Ik kreeg onlangs deze interviewvraag en ik ben benieuwd wat een goede oplossing hiervoor zou zijn.
Stel dat ik een 2D-array krijg waar alle
getallen in de array nemen toe
volgorde van links naar rechts en van boven naar
onderaan.Wat is de beste manier om te zoeken en
bepalen of een doelnummer in de staat
reeks?
Mijn eerste neiging is nu om een binaire zoekopdracht te gebruiken, aangezien mijn gegevens zijn gesorteerd. Ik kan bepalen of een getal in een enkele rij in O (log N) tijd staat. Het zijn echter de 2 richtingen die me afschrikken.
Een andere oplossing waarvan ik dacht dat die zou kunnen werken, is om ergens in het midden te beginnen. Als de middelste waarde kleiner is dan mijn doel, dan kan ik er zeker van zijn dat deze vanuit het midden in het linker vierkante gedeelte van de matrix staat. Ik beweeg dan diagonaal en controleer opnieuw, waarbij ik de grootte van het vierkant verklein dat het doelwit zou kunnen zijn totdat ik het doelnummer heb aangescherpt.
Heeft iemand goede ideeën om dit probleem op te lossen?
Voorbeeld array:
Van links naar rechts, van boven naar beneden gesorteerd.
1 2 4 5 6
2 3 5 7 8
4 6 8 9 10
5 8 9 10 11
Antwoord 1, autoriteit 100%
Hier is een eenvoudige benadering:
- Begin in de linkerbenedenhoek.
- Als het doel lager is dan die waarde, moet het boven ons staan, dus een hoger schuiven.
- Anders weten we dat het doel niet in die kolom kan staan, dus verplaats één naar rechts.
- Ga naar 2.
Voor een NxM-array wordt dit uitgevoerd in O(N+M). Ik denk dat het moeilijk zal zijn om het beter te doen. 🙂
Bewerken:Veel goede discussies. Ik had het over het algemene geval hierboven; duidelijk, als Nof Mklein zijn, zou je een binaire zoekbenadering kunnen gebruiken om dit te doen in iets dat de logaritmische tijd nadert.
Hier zijn enkele details, voor degenen die nieuwsgierig zijn:
Geschiedenis
Dit eenvoudige algoritme wordt een Saddleback Searchgenoemd. Het bestaat al een tijdje, en het is optimaal wanneer N == M. Enkele referenties:
- David Gries, De wetenschap van programmeren. Springer-Verlag, 1989.
- Edsgar Dijkstra, The Saddleback Search. Noot EWD-934, 1985.
Als N < Msuggereert intuïtie dat binair zoeken het beter zou moeten kunnen doen dan O(N+M): bijvoorbeeld wanneer N == 1, een pure binair zoeken wordt uitgevoerd in logaritmische in plaats van lineaire tijd.
In het ergste geval gebonden
Richard Bird onderzocht deze intuïtie dat binair zoeken het Saddleback-algoritme zou kunnen verbeteren in een paper uit 2006:
- Richard S. Bird, Het zoeken naar zadels verbeteren: een les in Algorithm Design, in Mathematics of Program Construction, pp. 82–89, volume 4014, 2006.
Met een nogal ongebruikelijke gesprekstechniek laat Bird ons zien dat voor N <= Mdit probleem een ondergrens heeft van Ω(N * log(M/N)). Deze grens is logisch, want het geeft ons lineaire prestaties wanneer N == Men logaritmische prestaties wanneer N == 1.
Algoritmen voor rechthoekige arrays
Een benadering die een binaire zoekactie per rij gebruikt, ziet er als volgt uit:
- Begin met een rechthoekige array waar
N < M. Laten we zeggen datNrijen is enMkolommen. - Voer een binaire zoekopdracht uit op de middelste rij voor
value. Als we het vinden, zijn we klaar. - Anders hebben we een aangrenzend paar getallen
senggevonden, waarbijs < value < g. - De rechthoek met getallen boven en links van
sis kleiner danvalue, dus we kunnen deze weglaten. - De rechthoek onder en rechts van
gis groter danvalue, dus we kunnen deze weglaten. - Ga naar stap (2) voor elk van de twee resterende rechthoeken.
In termen van complexiteit in het slechtste geval, doet dit algoritme log(M)het werk om de helft van de mogelijke oplossingen te elimineren, en roept zichzelf vervolgens recursief tweemaal op voor twee kleinere problemen. We moeten wel een kleinere versie van dat log(M)-werk voor elke rij herhalen, maar als het aantal rijen klein is in vergelijking met het aantal kolommen, dan kunnen we alle van die kolommen in logaritmische tijd begint de moeite waard te worden.
Dit geeft het algoritme een complexiteit van T(N,M) = log(M) + 2 * T(M/2, N/2), wat volgens Bird O(N * log(M/N)).
Een andere benadering gepost door Craig Gidneybeschrijft een algoritme dat vergelijkbaar is met de benadering hierboven: het onderzoekt rij voor rij met een stapgrootte van M/N. Uit zijn analyse blijkt dat dit ook resulteert in O(N * log(M/N))-prestaties.
Prestatievergelijking
Big-O-analyse is allemaal goed en wel, maar hoe goed werken deze benaderingen in de praktijk? De onderstaande grafiek onderzoekt vier algoritmen voor steeds “vierkante” arrays:
(Het “naïeve” algoritme doorzoekt eenvoudig elk element van de array. Het “recursieve” algoritme is hierboven beschreven. Het “hybride” algoritme is een implementatie van Gidney’s algoritme. Voor elke arraygrootte werden de prestaties gemeten door elk algoritme te timen over een vaste set van 1.000.000 willekeurig gegenereerde arrays.)
Enkele opvallende punten:
- Zoals verwacht bieden de algoritmen voor “binair zoeken” de beste prestaties op rechthoekige arrays en het Saddleback-algoritme werkt het beste op vierkante arrays.
- Het Saddleback-algoritme presteert slechter dan het ‘naïeve’ algoritme voor 1-d-arrays, vermoedelijk omdat het meerdere vergelijkingen maakt voor elk item.
- De prestatiehit die de algoritmen voor “binair zoeken” hebben op vierkante arrays, is vermoedelijk te wijten aan de overhead van het uitvoeren van herhaalde binaire zoekopdrachten.
Samenvatting
Slim gebruik van binair zoeken kan O(N * log(M/N)prestaties leveren voor zowel rechthoekige als vierkante arrays. De O(N + M)” zadelback”-algoritme is veel eenvoudiger, maar lijdt aan prestatievermindering omdat arrays steeds rechthoekig worden.
Antwoord 2, autoriteit 30%
Dit probleem kost Θ(b lg(t))tijd, waarbij b = min(w,h)en t=b/max(w,h). Ik bespreek de oplossing in deze blogpost.
Ondergrens
Een tegenstander kan een algoritme dwingen om Ω(b lg(t))-query’s te maken, door zichzelf te beperken tot de hoofddiagonaal:
Legende: witte cellen zijn kleinere items, grijze cellen zijn grotere items, gele cellen zijn kleinere of gelijke items en oranje cellen zijn grotere of gelijke items. De tegenstander dwingt de oplossing om de gele of oranje cel te zijn die het algoritme het laatst doorzoekt.
Merk op dat er bonafhankelijke gesorteerde lijsten met de grootte tzijn, waarvoor Ω(b lg(t))-query’s vereist zijn om volledig te elimineren.
Algoritme
- (Veronderstel zonder verlies van algemeenheid dat
w >= h) - Vergelijk het doelitem met de cel
tlinks van de rechterbovenhoek van het geldige gebied- Als het item van de cel overeenkomt, geeft u de huidige positie terug.
- Als het item van de cel kleiner is dan het doelitem, verwijder dan de resterende
t-cellen in de rij met een binaire zoekopdracht. Als een overeenkomend item wordt gevonden terwijl je dit doet, keer dan terug met zijn positie. - Anders is het celitem meer dan het doelitem, waardoor
tkorte kolommen worden geëlimineerd.
- Als er geen geldig gebied meer is, retourneer mislukt
- Ga naar stap 2
Een item zoeken:
Bepalen dat een item niet bestaat:
Legende: witte cellen zijn kleinere items, grijze cellen zijn grotere items en de groene cel is een gelijk item.
Analyse
Er zijn b*tkorte kolommen om te elimineren. Er zijn blange rijen om te elimineren. Het elimineren van een lange rij kost O(lg(t))tijd. Het elimineren van tkorte kolommen kost O(1)tijd.
In het ergste geval zullen we elke kolom en elke rij moeten elimineren, waarbij tijd nodig is O(lg(t)*b + b*t*1/t) = O(b lg(t)).
Houd er rekening mee dat ik aanneem dat lgvastloopt op een resultaat boven 1 (d.w.z. lg(x) = log_2(max(2,x))). Daarom krijgen we als w=h, wat t=1betekent, de verwachte grens van O(b lg(1)) = O(b) = O(w+h).
Code
public static Tuple<int, int> TryFindItemInSortedMatrix<T>(this IReadOnlyList<IReadOnlyList<T>> grid, T item, IComparer<T> comparer = null) {
if (grid == null) throw new ArgumentNullException("grid");
comparer = comparer ?? Comparer<T>.Default;
// check size
var width = grid.Count;
if (width == 0) return null;
var height = grid[0].Count;
if (height < width) {
var result = grid.LazyTranspose().TryFindItemInSortedMatrix(item, comparer);
if (result == null) return null;
return Tuple.Create(result.Item2, result.Item1);
}
// search
var minCol = 0;
var maxRow = height - 1;
var t = height / width;
while (minCol < width && maxRow >= 0) {
// query the item in the minimum column, t above the maximum row
var luckyRow = Math.Max(maxRow - t, 0);
var cmpItemVsLucky = comparer.Compare(item, grid[minCol][luckyRow]);
if (cmpItemVsLucky == 0) return Tuple.Create(minCol, luckyRow);
// did we eliminate t rows from the bottom?
if (cmpItemVsLucky < 0) {
maxRow = luckyRow - 1;
continue;
}
// we eliminated most of the current minimum column
// spend lg(t) time eliminating rest of column
var minRowInCol = luckyRow + 1;
var maxRowInCol = maxRow;
while (minRowInCol <= maxRowInCol) {
var mid = minRowInCol + (maxRowInCol - minRowInCol + 1) / 2;
var cmpItemVsMid = comparer.Compare(item, grid[minCol][mid]);
if (cmpItemVsMid == 0) return Tuple.Create(minCol, mid);
if (cmpItemVsMid > 0) {
minRowInCol = mid + 1;
} else {
maxRowInCol = mid - 1;
maxRow = mid - 1;
}
}
minCol += 1;
}
return null;
}
Antwoord 3, autoriteit 14%
Ik zou voor dit probleem de verdeel-en-heersstrategie gebruiken, vergelijkbaar met wat u voorstelde, maar de details zijn een beetje anders.
Dit is een recursieve zoekopdracht op subbereiken van de matrix.
Kies bij elke stap een element in het midden van het bereik. Als de gevonden waarde is wat u zoekt, bent u klaar.
Anders, als de gevonden waarde lager is dan de waarde die u zoekt, weet u dat deze zich niet in het kwadrant boven en links van uw huidige positie bevindt. Zoek dus recursief de twee subbereiken: alles (uitsluitend) onder de huidige positie, en alles (uitsluitend) rechts op of boven de huidige positie.
Anders (de gevonden waarde is groter dan de waarde die u zoekt) weet u dat deze niet in het kwadrant hieronder en rechts van uw huidige positie staat. Zoek dus recursief de twee subbereiken: alles (uitsluitend) links van de huidige positie, en alles (uitsluitend) boven de huidige positie die zich op de huidige kolom of een kolom rechts bevindt.
En ba-da-bing, je hebt het gevonden.
Houd er rekening mee dat elke recursieve aanroep alleen het huidige subbereik behandelt, niet (bijvoorbeeld) ALLE rijen boven de huidige positie. Alleen die in het huidige subbereik.
Hier is wat pseudocode voor je:
bool numberSearch(int[][] arr, int value, int minX, int maxX, int minY, int maxY)
if (minX == maxX and minY == maxY and arr[minX,minY] != value)
return false
if (arr[minX,minY] > value) return false; // Early exits if the value can't be in
if (arr[maxX,maxY] < value) return false; // this subrange at all.
int nextX = (minX + maxX) / 2
int nextY = (minY + maxY) / 2
if (arr[nextX,nextY] == value)
{
print nextX,nextY
return true
}
else if (arr[nextX,nextY] < value)
{
if (numberSearch(arr, value, minX, maxX, nextY + 1, maxY))
return true
return numberSearch(arr, value, nextX + 1, maxX, minY, nextY)
}
else
{
if (numberSearch(arr, value, minX, nextX - 1, minY, maxY))
return true
reutrn numberSearch(arr, value, nextX, maxX, minY, nextY)
}
Antwoord 4, autoriteit 5%
De twee belangrijkste antwoorden tot nu toe lijken de aantoonbare O(log N)“ZigZag-methode” en de O(N+M)Binaire zoekmethode te zijn. Ik dacht dat ik wat testen zou doen door de twee methoden te vergelijken met een aantal verschillende opstellingen. Hier zijn de details:
De array is in elke test N x N vierkant, waarbij N varieert van 125 tot 8000 (de grootste die mijn JVM-heap aankan). Voor elke arraygrootte heb ik een willekeurige plaats in de array gekozen om een enkele 2te plaatsen. Ik plaatste dan overal een 3(rechts en onder de 2) en vulde de rest van de array met 1. Sommige van de eerdere commentatoren leken te denken dat dit type setup de slechtste runtime voor beide algoritmen zou opleveren. Voor elke arraygrootte koos ik 100 verschillende willekeurige locaties voor de 2 (zoekdoel) en voerde de test uit. Ik heb de gemiddelde runtime en de worst case runtime voor elk algoritme geregistreerd. Omdat het te snel ging om goede ms-metingen in Java te krijgen, en omdat ik nanoTime( van Java) niet vertrouw, heb ik elke test 1000 keer herhaald om een uniforme biasfactor aan alle tijden toe te voegen. Dit zijn de resultaten:
ZigZag versloeg binair in elke test voor zowel gemiddelde als worst case tijden, maar ze liggen allemaal min of meer in een orde van grootte van elkaar.
Hier is de Java-code:
public class SearchSortedArray2D {
static boolean findZigZag(int[][] a, int t) {
int i = 0;
int j = a.length - 1;
while (i <= a.length - 1 && j >= 0) {
if (a[i][j] == t) return true;
else if (a[i][j] < t) i++;
else j--;
}
return false;
}
static boolean findBinarySearch(int[][] a, int t) {
return findBinarySearch(a, t, 0, 0, a.length - 1, a.length - 1);
}
static boolean findBinarySearch(int[][] a, int t,
int r1, int c1, int r2, int c2) {
if (r1 > r2 || c1 > c2) return false;
if (r1 == r2 && c1 == c2 && a[r1][c1] != t) return false;
if (a[r1][c1] > t) return false;
if (a[r2][c2] < t) return false;
int rm = (r1 + r2) / 2;
int cm = (c1 + c2) / 2;
if (a[rm][cm] == t) return true;
else if (a[rm][cm] > t) {
boolean b1 = findBinarySearch(a, t, r1, c1, r2, cm - 1);
boolean b2 = findBinarySearch(a, t, r1, cm, rm - 1, c2);
return (b1 || b2);
} else {
boolean b1 = findBinarySearch(a, t, r1, cm + 1, rm, c2);
boolean b2 = findBinarySearch(a, t, rm + 1, c1, r2, c2);
return (b1 || b2);
}
}
static void randomizeArray(int[][] a, int N) {
int ri = (int) (Math.random() * N);
int rj = (int) (Math.random() * N);
a[ri][rj] = 2;
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
if (i == ri && j == rj) continue;
else if (i > ri || j > rj) a[i][j] = 3;
else a[i][j] = 1;
}
}
}
public static void main(String[] args) {
int N = 8000;
int[][] a = new int[N][N];
int randoms = 100;
int repeats = 1000;
long start, end, duration;
long zigMin = Integer.MAX_VALUE, zigMax = Integer.MIN_VALUE;
long binMin = Integer.MAX_VALUE, binMax = Integer.MIN_VALUE;
long zigSum = 0, zigAvg;
long binSum = 0, binAvg;
for (int k = 0; k < randoms; k++) {
randomizeArray(a, N);
start = System.currentTimeMillis();
for (int i = 0; i < repeats; i++) findZigZag(a, 2);
end = System.currentTimeMillis();
duration = end - start;
zigSum += duration;
zigMin = Math.min(zigMin, duration);
zigMax = Math.max(zigMax, duration);
start = System.currentTimeMillis();
for (int i = 0; i < repeats; i++) findBinarySearch(a, 2);
end = System.currentTimeMillis();
duration = end - start;
binSum += duration;
binMin = Math.min(binMin, duration);
binMax = Math.max(binMax, duration);
}
zigAvg = zigSum / randoms;
binAvg = binSum / randoms;
System.out.println(findZigZag(a, 2) ?
"Found via zigzag method. " : "ERROR. ");
//System.out.println("min search time: " + zigMin + "ms");
System.out.println("max search time: " + zigMax + "ms");
System.out.println("avg search time: " + zigAvg + "ms");
System.out.println();
System.out.println(findBinarySearch(a, 2) ?
"Found via binary search method. " : "ERROR. ");
//System.out.println("min search time: " + binMin + "ms");
System.out.println("max search time: " + binMax + "ms");
System.out.println("avg search time: " + binAvg + "ms");
}
}
Antwoord 5, autoriteit 4%
Dit is een kort bewijs van de ondergrens van het probleem.
Je kunt het niet beter doen dan lineaire tijd (in termen van array-dimensies, niet het aantal elementen). In de onderstaande array kan elk van de elementen gemarkeerd als *5 of 6 zijn (onafhankelijk van andere). Dus als uw doelwaarde 6 (of 5) is, moet het algoritme ze allemaal onderzoeken.
1 2 3 4 *
2 3 4 * 7
3 4 * 7 8
4 * 7 8 9
* 7 8 9 10
Natuurlijk wordt dit ook uitgebreid naar grotere arrays. Dit betekent dat dit antwoordis optimaal.
Update: zoals opgemerkt door Jeffrey L Whitledge, is het alleen optimaal als de asymptotische ondergrens van looptijd versus invoergegevensgrootte (behandeld als een enkele variabele). De looptijd die wordt behandeld als een functie met twee variabelen op beide array-dimensies kan worden verbeterd.
Antwoord 6, autoriteit 3%
Volgens mij is hier het antwoord en het werkt voor elke soort gesorteerde matrix
bool findNum(int arr[][ARR_MAX],int xmin, int xmax, int ymin,int ymax,int key)
{
if (xmin > xmax || ymin > ymax || xmax < xmin || ymax < ymin) return false;
if ((xmin == xmax) && (ymin == ymax) && (arr[xmin][ymin] != key)) return false;
if (arr[xmin][ymin] > key || arr[xmax][ymax] < key) return false;
if (arr[xmin][ymin] == key || arr[xmax][ymax] == key) return true;
int xnew = (xmin + xmax)/2;
int ynew = (ymin + ymax)/2;
if (arr[xnew][ynew] == key) return true;
if (arr[xnew][ynew] < key)
{
if (findNum(arr,xnew+1,xmax,ymin,ymax,key))
return true;
return (findNum(arr,xmin,xmax,ynew+1,ymax,key));
} else {
if (findNum(arr,xmin,xnew-1,ymin,ymax,key))
return true;
return (findNum(arr,xmin,xmax,ymin,ynew-1,key));
}
}
Antwoord 7
Interessante vraag. Overweeg dit idee – maak een grens waar alle getallen groter zijn dan je doel en een andere waar alle getallen kleiner zijn dan je doel. Als er iets tussen de twee blijft, is dat je doelwit.
Als ik in uw voorbeeld naar 3 zoek, lees ik over de eerste rij totdat ik 4 raak, en zoek dan naar het kleinste aangrenzende getal (inclusief diagonalen) groter dan 3:
1 2 45 6
2 3 57 8
4 68 9 10
5 8 9 10 11
Nu doe ik hetzelfde voor die getallen kleiner dan 3:
1 2 45 6
23 57 8
4 68 9 10
5 8 9 10 11
Nu vraag ik, is er iets binnen de twee grenzen? Zo ja, dan moet het 3 zijn. Zo nee, dan is er geen 3. Een beetje indirect, aangezien ik het nummer niet echt kan vinden, concludeer ik gewoon dat het daar moet zijn. Dit heeft de toegevoegde bonus van het tellen van ALLE 3’s.
Ik heb dit bij enkele voorbeelden geprobeerd en het lijkt goed te werken.
Antwoord 8
Binair zoeken via de diagonaal van de array is de beste optie.
We kunnen achterhalen of het element kleiner is dan of gelijk is aan de elementen in de diagonaal.
Antwoord 9
Ik stel deze vraag al bijna tien jaar in interviews en ik denk dat er maar één persoon is geweest die een optimaal algoritme heeft kunnen bedenken.
Mijn oplossing is altijd geweest:
-
Binair zoeken in de middelste diagonaal, de diagonaal die naar beneden en naar rechts loopt, met het item op
(rows.count/2, columns.count/2). -
Als het doelnummer is gevonden, retourneer dan waar.
-
Anders zijn er twee getallen (
uenv) gevonden zodatukleiner is dan het doel,vis groter dan het doel, envis één rechts en één lager danu. -
Recursief zoeken in de submatrix rechts van
uen bovenaanven die onderuen links vanv.
Ik geloof dat dit een strikte verbetering is ten opzichte van het algoritme gegeven door Nate here, aangezien zoeken op de diagonaal vaak een reductie mogelijk maakt van meer dan de helft van de zoekruimte (als de matrix bijna vierkant is), terwijl zoeken in een rij of kolom altijd een eliminatie van precies de helft oplevert.
Hier is de code in (waarschijnlijk niet erg Swifty) Swift:
import Cocoa
class Solution {
func searchMatrix(_ matrix: [[Int]], _ target: Int) -> Bool {
if (matrix.isEmpty || matrix[0].isEmpty) {
return false
}
return _searchMatrix(matrix, 0..<matrix.count, 0..<matrix[0].count, target)
}
func _searchMatrix(_ matrix: [[Int]], _ rows: Range<Int>, _ columns: Range<Int>, _ target: Int) -> Bool {
if (rows.count == 0 || columns.count == 0) {
return false
}
if (rows.count == 1) {
return _binarySearch(matrix, rows.lowerBound, columns, target, true)
}
if (columns.count == 1) {
return _binarySearch(matrix, columns.lowerBound, rows, target, false)
}
var lowerInflection = (-1, -1)
var upperInflection = (Int.max, Int.max)
var currentRows = rows
var currentColumns = columns
while (currentRows.count > 0 && currentColumns.count > 0 && upperInflection.0 > lowerInflection.0+1) {
let rowMidpoint = (currentRows.upperBound + currentRows.lowerBound) / 2
let columnMidpoint = (currentColumns.upperBound + currentColumns.lowerBound) / 2
let value = matrix[rowMidpoint][columnMidpoint]
if (value == target) {
return true
}
if (value > target) {
upperInflection = (rowMidpoint, columnMidpoint)
currentRows = currentRows.lowerBound..<rowMidpoint
currentColumns = currentColumns.lowerBound..<columnMidpoint
} else {
lowerInflection = (rowMidpoint, columnMidpoint)
currentRows = rowMidpoint+1..<currentRows.upperBound
currentColumns = columnMidpoint+1..<currentColumns.upperBound
}
}
if (lowerInflection.0 == -1) {
lowerInflection = (upperInflection.0-1, upperInflection.1-1)
} else if (upperInflection.0 == Int.max) {
upperInflection = (lowerInflection.0+1, lowerInflection.1+1)
}
return _searchMatrix(matrix, rows.lowerBound..<lowerInflection.0+1, upperInflection.1..<columns.upperBound, target) || _searchMatrix(matrix, upperInflection.0..<rows.upperBound, columns.lowerBound..<lowerInflection.1+1, target)
}
func _binarySearch(_ matrix: [[Int]], _ rowOrColumn: Int, _ range: Range<Int>, _ target: Int, _ searchRow : Bool) -> Bool {
if (range.isEmpty) {
return false
}
let midpoint = (range.upperBound + range.lowerBound) / 2
let value = (searchRow ? matrix[rowOrColumn][midpoint] : matrix[midpoint][rowOrColumn])
if (value == target) {
return true
}
if (value > target) {
return _binarySearch(matrix, rowOrColumn, range.lowerBound..<midpoint, target, searchRow)
} else {
return _binarySearch(matrix, rowOrColumn, midpoint+1..<range.upperBound, target, searchRow)
}
}
}
Antwoord 10
A. Voer een binaire zoekopdracht uit op die regels waar het doelnummer zou kunnen staan.
B. Maak er een grafiek van: zoek het getal door altijd het kleinste niet-bezochte buurknooppunt te nemen en terug te gaan wanneer een te groot getal wordt gevonden
Antwoord 11
Binair zoeken zou de beste aanpak zijn, imo. Beginnend bij 1/2 x, zal 1/2 y het in tweeën snijden. D.w.z. een 5×5 vierkant zou zoiets zijn als x == 2 / y == 3 . Ik heb een waarde naar beneden en een waarde naar boven afgerond om een betere zone in de richting van de beoogde waarde te krijgen.
Voor de duidelijkheid zou de volgende iteratie je zoiets geven als x == 1 / y == 2 OF x == 3 / y == 5
Antwoord 12
Nou, laten we om te beginnen aannemen dat we een vierkant gebruiken.
1 2 3
2 3 4
3 4 5
1. Een vierkant zoeken
Ik zou een binaire zoekopdracht op de diagonaal gebruiken. Het doel is om het kleinere getal te vinden dat niet strikt lager is dan het doelnummer.
Stel dat ik bijvoorbeeld op zoek ben naar 4, dan zou ik uiteindelijk 5vinden op (2,2).
Dan ben ik er zeker van dat als 4in de tabel staat, het op een positie staat ofwel (x,2)of (2,x)met xin [0,2]. Nou, dat zijn slechts 2 binaire zoekopdrachten.
De complexiteit is niet ontmoedigend: O(log(N))(3 binaire zoekopdrachten op lengtebereiken N)
2. Een rechthoek zoeken, naïeve benadering
Natuurlijk wordt het een beetje ingewikkelder wanneer Nen Mverschillen (met een rechthoek), overweeg dit gedegenereerde geval:
1 2 3 4 5 6 7 8
2 3 4 5 6 7 8 9
10 11 12 13 14 15 16 17
En laten we zeggen dat ik op zoek ben naar 9… De diagonale benadering is nog steeds goed, maar de definitie van diagonale veranderingen. Hier is mijn diagonaal [1, (5 or 6), 17]. Laten we zeggen dat ik [1,5,17]heb opgepikt, dan weet ik dat als 9in de tabel staat, het in het subgedeelte staat:
5 6 7 8
6 7 8 9
10 11 12 13 14 15 16
Dit geeft ons 2 rechthoeken:
5 6 7 8 10 11 12 13 14 15 16
6 7 8 9
Dus we kunnen recurren! waarschijnlijk beginnend met degene met minder elementen (hoewel het ons in dit geval doodt).
Ik moet erop wijzen dat als een van de dimensies kleiner is dan 3, we de diagonale methoden niet kunnen toepassen en een binaire zoekopdracht moeten gebruiken. Hier zou het betekenen:
- Binnenair zoeken toepassen op
10 11 12 13 14 15 16, niet gevonden - Binnenair zoeken toepassen op
5 6 7 8, niet gevonden - Binnenair zoeken toepassen op
6 7 8 9, niet gevonden
Het is lastig, want om goede prestaties te krijgen, wilt u misschien onderscheid maken tussen verschillende gevallen, afhankelijk van de algemene vorm….
3. Op zoek naar een rechthoekige, brutale aanpak
Het zou veel gemakkelijker zijn als we met een vierkant te maken hadden… dus laten we de zaken gewoon op een rijtje zetten.
1 2 3 4 5 6 7 8
2 3 4 5 6 7 8 9
10 11 12 13 14 15 16 17
17 . . . . . . 17
. .
. .
. .
17 . . . . . . 17
We hebben nu een vierkant.
Natuurlijk zullen we die rijen waarschijnlijk NIET echt maken, we kunnen ze gewoon emuleren.
def get(x,y):
if x < N and y < M: return table[x][y]
else: return table[N-1][M-1] # the max
het gedraagt zich dus als een vierkant zonder meer geheugen in beslag te nemen (ten koste van de snelheid, waarschijnlijk, afhankelijk van de cache… ach :p)
Antwoord 13
BEWERKEN:
Ik heb de vraag verkeerd begrepen. Zoals de opmerkingen aangeven, werkt dit alleen in het meer beperkte geval.
In een taal als C die gegevens in rij-hoofdvolgorde opslaat, behandelt u deze eenvoudig als een 1D-array met de grootte n * m en gebruikt u een binaire zoekopdracht.
Antwoord 14
Ik heb een recursieve Divide & Verover oplossing.
Het basisidee voor één stap is: We weten dat de Links-Bovenste(LU) het kleinst is en de rechts-onder(RB) het grootste getal, dus het gegeven No(N) moet: N>=LU en N<= RB
IF N==LU en N==RB::::Element gevonden en afgebroken om de positie/index terug te geven
Als N>=LU en N<=RB = FALSE, is Nee er niet en wordt afgebroken.
Als N>=LU en N<=RB = TRUE, verdeel de 2D-array dan op een logische manier in 4 gelijke delen van de 2D-array.
En pas dan dezelfde algostap toe op alle vier de subarrays.
Mijn Algo is correct die ik heb geïmplementeerd op de pc van mijn vriend.
Complexiteit: elke 4 vergelijkingen kunnen worden gebruikt om het totale aantal elementen in het slechtste geval af te leiden tot een vierde.
Dus mijn complexiteit wordt 1 + 4 x lg(n) + 4
Maar verwachtte echt dat dit zou werken aan O(n)
Ik denk dat er ergens iets mis is in mijn berekening van Complexiteit, corrigeer dit alstublieft als dat zo is..
Antwoord 15
De optimale oplossing is om in de linkerbovenhoek te beginnen, dat heeft een minimale waarde. Beweeg diagonaal naar rechts naar beneden totdat je een element raakt waarvan de waarde >= waarde van het gegeven element. Als de waarde van het element gelijk is aan die van het gegeven element, retourneer dan gevonden als waar.
Anders kunnen we vanaf hier op twee manieren verder.
Strategie 1:
- Ga omhoog in de kolom en zoek naar het gegeven element totdat we het einde hebben bereikt. Indien gevonden, retourneer gevonden als waar
- Ga naar links in de rij en zoek naar het gegeven element totdat we het einde bereiken. Indien gevonden, retourneer gevonden als waar
- retour gevonden als onwaar
Strategie 2:
Laat ik de rijindex aangeven en j de kolomindex van het diagonale element waar we bij zijn gestopt. (Hier hebben we i = j, BTW). Laat k = 1.
- Herhaal de onderstaande stappen totdat i-k >= 0
- Zoek of a[i-k][j] gelijk is aan het gegeven element. zo ja, retourneer gevonden als waar.
- Zoek of a[i][j-k] gelijk is aan het gegeven element. zo ja, retourneer gevonden als waar.
- Verhogen k
1 2 4 5 6
2 3 5 7 8
4 6 8 9 10
5 8 9 10 11
Antwoord 16
public boolean searchSortedMatrix(int arr[][] , int key , int minX , int maxX , int minY , int maxY){
// base case for recursion
if(minX > maxX || minY > maxY)
return false ;
// early fails
// array not properly intialized
if(arr==null || arr.length==0)
return false ;
// arr[0][0]> key return false
if(arr[minX][minY]>key)
return false ;
// arr[maxX][maxY]<key return false
if(arr[maxX][maxY]<key)
return false ;
//int temp1 = minX ;
//int temp2 = minY ;
int midX = (minX+maxX)/2 ;
//if(temp1==midX){midX+=1 ;}
int midY = (minY+maxY)/2 ;
//if(temp2==midY){midY+=1 ;}
// arr[midX][midY] = key ? then value found
if(arr[midX][midY] == key)
return true ;
// alas ! i have to keep looking
// arr[midX][midY] < key ? search right quad and bottom matrix ;
if(arr[midX][midY] < key){
if( searchSortedMatrix(arr ,key , minX,maxX , midY+1 , maxY))
return true ;
// search bottom half of matrix
if( searchSortedMatrix(arr ,key , midX+1,maxX , minY , maxY))
return true ;
}
// arr[midX][midY] > key ? search left quad matrix ;
else {
return(searchSortedMatrix(arr , key , minX,midX-1,minY,midY-1));
}
return false ;
}
Antwoord 17
Ik raad aan om alle tekens op te slaan in een 2D list. zoek dan de index van het vereiste element als het in de lijst bestaat.
Indien niet aanwezig, print het juiste bericht anders print rij en kolom als:
row = (index/total_columns)en column = (index%total_columns -1)
Dit zal alleen de binaire zoektijd in een lijst opleveren.
Stel eventuele correcties voor. 🙂
Antwoord 18
Als O(M log(N))de oplossing oké is voor een MxN-array –
template <size_t n>
struct MN * get(int a[][n], int k, int M, int N){
struct MN *result = new MN;
result->m = -1;
result->n = -1;
/* Do a binary search on each row since rows (and columns too) are sorted. */
for(int i = 0; i < M; i++){
int lo = 0; int hi = N - 1;
while(lo <= hi){
int mid = lo + (hi-lo)/2;
if(k < a[i][mid]) hi = mid - 1;
else if (k > a[i][mid]) lo = mid + 1;
else{
result->m = i;
result->n = mid;
return result;
}
}
}
return result;
}
Laat het me weten als dit niet werkt of als er een bug is.
Antwoord 19
Gegeven een vierkante matrix als volgt:
[ a b c ] [ d e f ] [ ik j k ]
We weten dat een < c, d < f, ik < k. Wat we niet weten, is of d < c of d > c, enz. We hebben alleen garanties in 1-dimensie.
Kijkend naar de eindelementen (c,f,k), kunnen we een soort filter maken: is N < C ? zoek() : volgende(). We hebben dus n iteraties over de rijen, waarbij elke rij ofwel O( log(n)) neemt voor binair zoeken of O( 1 ) indien uitgefilterd.
Laat me een VOORBEELD geven waarbij N = j,
1) Controleer rij 1. j < C? (nee, ga verder)
2) Controleer rij 2. j < F? (ja, zoeken in bin levert niets op)
3) Controleer rij 3. j < k? (ja, bin search vindt het)
Probeer het opnieuw met N = q,
1) Controleer rij 1. q < C? (nee, ga verder)
2) Controleer rij 2. q < F? (nee, ga verder)
3) Controleer rij 3. q < k? (nee, ga verder)
Er is waarschijnlijk een betere oplossing, maar deze is gemakkelijk uit te leggen.. 🙂
Antwoord 20
Aangezien dit een interviewvraag is, lijkt deze te leiden tot een discussie over Parallel programmeren en Map-reduce-algoritmen.
Zie http://code.google.com/intl /de/edu/parallel/mapreduce-tutorial.html