De retour de la position de la valeur dans un tableau 2D, Java

Je suis fatigué. Ce doit être simple. de bois... pour.... les arbres....

Je suis en train de retourner la position d'une valeur dans un tableau 2D.

J'ai un double tableau [300][300].

Toutes les valeurs contenues dans ce document sont 0 à l'exception d'une qui est de 255.

Comment puis-je écrire une méthode pour retourner [i][j] emplacement de 255?

Merci d'avance.

  • Ces valeurs sont triées? Si donc, il y O(log n) (complètement trié) ou O(n log n) (uniquement les lignes ou de colonnes) versions. Sinon, vous êtes coincé avec O(n^2), comme cela a été prévu.
  • Non, pas triés.
  • que faire de ces O choses à dire. Ils n'ont pas de sens pour moi et donc je ne comprends pas leur valeur
  • il s'appelle Big O la notation. C'est un moyen simple de mesurer le nombre d'étapes nécessaires pour faire quelque chose.
InformationsquelleAutor Oliver Burdekin | 2011-12-06
  1. 3

    Simplement parcourir tous les éléments jusqu'à ce que vous trouviez celui qui est 255:

    for ( int i = 0; i < 300; ++i ) {
    for ( int j = 0; j < 300; ++j ) {
        if ( array[i][j] == 255 ) {
            //Found the correct i,j - print them or return them or whatever
        } 
    }
}
    • Salut Extorsion et merci beaucoup pour votre aide. J'avais atteint ce point, mais avait de la difficulté à retourner à la fois les nombres entiers. c'est à dire si [150][200] qui a eu lieu 255 comment pourrais-je le retour de ces deux entiers pour ensuite utiliser ailleurs? Une fois que j'ai l'emplacement que je puis avoir besoin d'utiliser ces deux comme les deux premiers emplacements dans un tableau 3D ([150][200][75]). /**Pouvez-vous dire que je suis un newb?**/
    • Si vous souhaitez retourner, vous auriez à les mettre dans un tableau ou faire un objet à la fois d'eux. Ou, vous pouvez définir certaines variables de classe en interne dans la méthode (et ne retourne rien), bien que je n'aime pas ça. Une autre option est de laisser ceux que je,j variables à l'intérieur de cette méthode et il suffit de passer à une autre méthode qui utilise ensuite ces pour de plus amples indexation.
    • Brillant. Merci encore!
    InformationsquelleAutor Nate W.
  2. 2

    Cela fonctionne:

    public int[] get255() {
  for(int i = 0; i < array.length; i++)
    for(int j = 0; j < (array[i].length/2)+1; j++)
      if(array[i][j] == 255)
        return new int[] {i,j};
      else if(array[j][i] == 255) //This just slightly increases efficiency
        return new int[] {j,i};
  return null; //If not found, return null
}

    C'est peut-être le plus rapide, cependant. Il vérifie de départ dans chaque coin, progressivement vers l'intérieur vers le centre, horizontalement d'abord, puis verticalement:

    public int[] get255() {
  for(int i = 0; i < (array.length/2)+1; i++)
    for(int j = 0; j < (array[i].length/2)+1; j++)
      //Check the top-left
      if(array[i][j] == 255)
        return new int[] {i,j};

      //Check the bottom-left
      else if(array[array.length-i][j] == 255)
        return new int[] {array.length-i,j};

      //Check the top-right
      else if(array[i][array[i].length-j] == 255)
        return new int[] {i,array[i].length-j};

      //Check the bottom-right
      else if(array[array.length-i][array[i].length-j])
        return new int[] {array.length-i, array[i].length-j};

  return null; //If not found, return null
}
    • Ne serait-ce pas vérifier chaque élément deux fois si 255 n'est pas dans le tableau?
    • oui, mais si vous pouvez supposer que 255 seront dans le tableau, il a près d'une réduction de 25% du temps au mieux.
    • Eh bien, vous pourriez juste itérer i=0..length/2 et j=0..length/2 à la place pour éviter une double vérification. (Peut-être des tout-en-un)
    • je ne sais pas pourquoi j'ai oublié à ce sujet, a ajouté maintenant. Ajout également d'une sécurité avec .length/2+1. i a parcourir toute la longueur, bien que.
    • Ce n'est pas plus efficace si. Vous êtes toujours en train de faire le même nombre de comparaisons que l'Adaptation de la réponse (n^2).
    • n^2 est pire-cas. La moyenne des cas est encore plus rapide car il vérifie les deux côtés avant de le ré-itération. Le plus efficace peut comprendre plus de deux contrôles (et en ajoutant un deuxième exemple de code).
    • En moyenne, il itère de moins en moins de temps. Je suis en train de dire qu'il fait le même nombre de comparaisons, compte tenu des données aléatoires. Si 255 tend à se produire plus souvent sur la "fin" de la matrice, ce sera plus efficace. Toutefois, si 255 tend à se produire plus dans le milieu de la rangée, puis de l'Adaptation de la réponse permettra de faire la moitié du nombre de comparaisons que votre algorithme. Donc, je pense que l'optimisation de cet algorithme, nous allons avoir besoin de savoir plus d'informations sur le jeu de données.
    • laissez-nous continuer cette discussion dans le chat

    InformationsquelleAutor Jon Egeland
  3. 0

    Vous pouvez utiliser la recherche binaire pour chaque colonne.

    Utilisation pour boucle d'itération sur chaque colonne comme c'est un tableau 2d.

    Une fois que vous obtenez toutes les lignes de la colonne de l'itération ( ce qui serait un autre tableau), faire une recherche binaire sur eux.

    Conditions S'Appliquent:
    1. Si le tableau est trié .
    2. Si vous êtes sûr qu'un seul élément est-il dans chaque colonne. ( Pas de doublons).
    3. Si il y a des doublons dans les lignes( faire la recherche linéaire) .

    J'espère que cela aide. N'hésitez pas à demander si elle est encore dans le doute 🙂

    InformationsquelleAutor Prannoy Tank