Retourpositie van waarde in een 2D-array, Java

Ik ben moe. Dit moet eenvoudig zijn. hout ... voor .... bomen ....

Ik probeer de positie van een specifieke waarde in een 2D-array te retourneren.

Ik heb een dubbele array [300] [300].

Alle waarden die erin staan ​​zijn 0 behalve een waarde die 255 is.

Hoe schrijf ik een methode om de [i] [j] -locatie van 255 te retourneren?

Bij voorbaat dank.

0
Zijn deze waarden gesorteerd? Als dit het geval is, zijn er O (log n) (volledig gesorteerd) of O (n log n) (alleen rijen of kolommen gesorteerd) versies. Anders zit je vast met O (n ^ 2) , zoals is verstrekt.
toegevoegd de auteur Clockwork-Muse, de bron
@JohnnyCoder - dit wordt Big O-notatie genoemd. Het is een eenvoudige maatstaf voor het verwachte aantal stappen dat nodig is om iets te doen.
toegevoegd de auteur Clockwork-Muse, de bron
@ Clockwork-Muse wat betekenen deze O-dingen. Ze kloppen nergens voor en ik begrijp hun waarde dus niet
toegevoegd de auteur Ungeheuer, de bron
Nee, niet gesorteerd.
toegevoegd de auteur Oliver Burdekin, de bron

3 antwoord

Simpelweg alle elementen itereren tot u degene vindt die 255 is:

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
        } 
    }
}
3
toegevoegd
@OliverBurdekin: als je ze wilt retourneren, moet je ze in een array plaatsen of een object maken dat beide bevat. Of je kunt intern een aantal klassenvariabelen in die methode instellen (en niets retourneren), hoewel ik dit niet leuk vind. Een andere optie is om die i, j variabelen in die methode achter te laten en deze gewoon door te geven aan een andere methode die deze vervolgens gebruikt voor verdere indexering.
toegevoegd de auteur Nate W., de bron
Hallo Shakedown en heel erg bedankt voor je hulp. Ik was op dit punt aangekomen maar had problemen met het retourneren van beide gehele getallen. d.w.z. als [150] [200] 255 vasthield, hoe zou ik die twee gehele getallen dan retourneren om ze vervolgens ergens anders te gebruiken? Zodra ik de locatie heb, moet ik deze twee gebruiken als de eerste twee locaties in een 3D-array ([150] [200] [75])./** Kun je zien dat ik een nieuweling ben? ** /
toegevoegd de auteur Oliver Burdekin, de bron
Briljant. Nogmaals bedankt!
toegevoegd de auteur Oliver Burdekin, de bron

Dit werkt:

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
}

Dit is misschien wel de snelste. Het controleert in elke hoek, en werkt progressief naar binnen naar het centrum, eerst horizontaal en daarna verticaal:

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
}
2
toegevoegd
Zou dit niet elk element twee keer controleren als 255 niet in de array zit?
toegevoegd de auteur skyuzo, de bron
U kunt in plaats daarvan i = 0..length/2 en j = 0..length/2 herhalen om dubbele controle te voorkomen. (Misschien een voor een)
toegevoegd de auteur skyuzo, de bron
Dit is misschien niet echt efficiënter. Je maakt nog steeds hetzelfde aantal vergelijkingen als het antwoord van Shakedown (n ^ 2).
toegevoegd de auteur skyuzo, de bron
Gemiddeld itereert het minder vaak. Ik zeg dat het hetzelfde aantal vergelijkingen maakt, gegeven willekeurige gegevens. Als 255 vaker voorkomt aan de "uiteinden" van de array, dan is dit efficiënter. Als 255 echter meer voorkomt in het midden van de array, maakt het antwoord van Shakedown half zoveel vergelijkingen als uw algoritme. Dus ik vermoed dat we, om dit algoritme te optimaliseren, wat meer informatie over de dataset nodig hebben.
toegevoegd de auteur skyuzo, de bron
Ja, maar als je kunt aannemen dat er 255 in de array zit, heeft dit op zijn best een reductie van 25% in de tijd.
toegevoegd de auteur Jon, de bron
@skyuzo weet niet waarom ik dat ben vergeten, nu toegevoegd. Ook een veiligheid toegevoegd met .length/2 + 1 . i moet echter de volledige lengte doorlopen.
toegevoegd de auteur Jon, de bron
n ^ 2 is in het slechtste geval. De gemiddelde behuizing is nog steeds sneller omdat het beide zijden controleert voordat het opnieuw wordt gebruikt. De meest efficiënte kan nog twee controles bevatten (toevoegen als een tweede codevoorbeeld).
toegevoegd de auteur Jon, de bron
toegevoegd de auteur Jon, de bron

U kunt binaire zoekopdrachten voor elke kolom gebruiken.

Gebruik de lus voor om over elke kolom te itereren aangezien het een 2D-array is.

Zodra u alle rijen uit de specifieke kolom krijgt die u itereert (wat een andere array zou zijn), voert u een binaire zoekopdracht uit.

Conditions Apply: 1. If the array is sorted . 2. If you are sure that only one element is there in each column. ( No duplicates). 3. If there are duplicates in the rows( do linear search) .

Ik hoop dat het helpt. Gelieve te voelen vrij om te vragen of nog steeds in geval van twijfel :)

0
toegevoegd