Effiziente Methode zum Zählen von Vorkommen eines Schlüssels in einem sortierten Array

Question

Dies wurde in Microsoft-Vor-Ort-Interview gefragt.

Zählen Sie die Anzahl der Vorkommen eines bestimmten Schlüssels in einem Array.

Ich antwortete lineare Suche, weil die Elemente im Array verstreut sein können. Angenommen, der Schlüssel befindet sich am Anfang und am Ende. So müssen wir das gesamte Array scannen.

Als nächstes fragte er, was, wenn das Array sortiert ist?

Dachte für eine Weile und sagte, ich werde lineare Suche wieder verwenden. Weil die Wiederholungen des Schlüssels, falls vorhanden, irgendwo im Array sein können. Als eine Optimierung habe ich auch gesagt, wenn erste und letzte Array-Elemente gleich sind, können Sie die Array-Länge als Antwort nehmen.

Ist meine Analyse in beiden Fällen korrekt?

Beispiel:

Input = [0 0 1 1 1 2 2 3 3], key = 1, Answer = 3 
Input = [0 0 2 2 3 3],  key = 1, Answer = 0 

Answer 1

Wenn das Array unsortiert ist, ja, lineare Suche von einem Ende zum anderen ist so gut wie es geht.

Wenn das Array jedoch sortiert ist, können Sie bessere Ergebnisse erzielen als lineare Zeit, indem Sie Binär- oder Interpolationssuchverfahren anwenden.

Behandeln Sie das Problem wie "Suchen Sie die Nummer X in einer sortierten Liste" mit dem hinzugefügten Detail von "dann scannen Sie nach links und rechts, um zu bestimmen, wie oft X erscheint". Der erste Teil, die Suche, wird am besten mit Binär- oder Interpolationssuche durchgeführt.

http://en.wikipedia.org/wiki/Interpolation_search

http://en.wikipedia.org/wiki/Binary_search

Answer 2

Ja, du hast Recht für unsortierte Array, aber für sortiertes Array können Sie binäre Suche verwenden ein Vorkommen des Elements zu lokalisieren und einmal, dass ein Vorkommen gefunden wird nur scannen angrenzend Elemente, bis Sie Unstimmigkeiten finden und dann aufhören.

Answer 3

Für unsortiertes Array können wir nicht viel anderes als lineare Suche tun.

Für sortiertes Array können Sie es in O(logN) tun, um eine leicht modifizierte binäre Suche:

• Finden Sie den Index des ersten Auftretens von key, nennen es f.
• Suchen Sie den Index des letzten Auftretens von key, nennen Sie es l.
• Wenn die key im Array existiert l-f+1 ist die Antwort.

das erste Vorkommen Finding:

arr[i] ist das erste Auftreten von key iff

• arr[i] == keyund entweder
  • i == 0 (es ist das erste Element der das Array) oder
  • arr[i-1] != key (es ist nicht das erste Element des Arrays und Element es übrig bleibt, ist unterschiedlich)

Sie können leicht die binäre Suche ändern das erste Vorkommen zu finden.
In einer binären Suche beenden Sie die Suche, wenn Sie arr[mid] == key finden.
die Bedingung ändern, so dass Sie die Suche beenden, wenn Sie die erste Auftreten statt jede Vorkommen finden.

Algorithmus:

low = 0 
high = arrSize - 1 

while low <= high 

    mid = (low + high)/2 

    //if arr[mid] == key   // CHANGE 
    if arr[mid] == key AND (mid == 0 OR arr[mid-1] != key) 
    return mid 
    //else if (key < arr[mid]) // CHANGE 
    else if (key <= arr[mid]) 
    high = mid - 1 
    else 
    low = mid + 1   
    end-if 

end-while 

return -1 

Ebenso können Sie das letzte Vorkommen finden.

Answer 4

Für einmal werde ich eine Implementierung in C++ vorschlagen.

size_t count(std::vector<int> const& vec, int key) 
{ 
    auto p = std::equal_range(vec.begin(), vec.end(), key); 
    return std::distance(p.first, p.second); 
} 

equal_range eine binäre Suche verwendet, ist das Ergebnis gleich:

std::make_pair(std::lower_bound(vec.begin(), vec.end(), key), 
       std::upper_bound(vec.begin(), vec.end(), key); 

aber die Umsetzung sollte macht es schneller leicht, obwohl alle in O sind (log N) (in Bezug auf die Anzahl Vergleich).

Answer 5

können Sie rekursive Version der binären Suche verwenden

int modifiedbinsearch_low(int* arr, int low, int high , int key) 
{ 
    if(low==high) return high ; 

    int mid = low + (high-low) /2; 

    if(key > arr[mid]) { modifiedbinsearch_low(arr,mid + 1 , high,key); } 
    else { modifiedbinsearch_low(arr,low,mid,key); } 
} 
int modifiedbinsearch_high(int* arr, int low, int high , int key) 
{ 
    if(low==high) return high ; 

    int mid = low + (high-low) /2; 

    if(key < arr[mid]) { modifiedbinsearch_high(arr,low,mid,key); } 
    else { modifiedbinsearch_high(arr,mid+1,high,key); } 

} 

.

int low = modifiedbinsearch_low(...) 

int high = modifiedbinsearch_high(...) 

(high - low) gibt die Anzahl der Tasten

Answer 6

** Zeitkomplexität = O (lg N), wobei N die Größe des Arrays ist

** Argumente für binarySearchXXXXX: **

1. int [] Array ist ein sortiertes Array der Länge> = 1
2. int k: key

**

package array; 

public class BinarySearchQuestion { 

public static int binarySearchFirst(int[] array, int k) { 
    int begin = 0; 
    int end = array.length-1; 
    int mid = -1; 
    while (begin <= end) { 
     mid = begin + (end - begin)/2; 
     if (array[mid] < k) { 
      begin = mid + 1; 
     } else { 
      end = mid - 1; 
     } 
    } 
    //System.out.println("Begin index :: " + begin + " , array[begin] " + array[begin]); 
    return (begin <= array.length - 1 && begin >= 0 && array[begin] != k) ? -1 : begin; 
    //  return begin; 
} 

public static int binarySearchLast(int[] array, int k) { 
    int begin = 0; 
    int end = array.length - 1; 
    int mid = -1; 
    while (begin <= end) { 
     mid = begin + (end - begin)/2; 
     if (array[mid] > k) { 
      end = mid - 1; 
     } else { 
      begin = mid + 1; 
     } 
    } 
    //System.out.println("Last index end :: " + end + " , array[mid] " + array[end]); 
    return (end <= array.length - 1 && end >= 0 && array[end] != k) ? -1 : end; 
    //return end; 
} 

/** 
* @param args 
*/ 
public static void main(String[] args) { 
      //  int[] array = { 0, 1,1,1, 2, 3, 4,4,4,5, 5, 5, 5, 5, 5, 5, 5, 5, 5,5,6,6,6,6, 6, 7, 7, 7, 
      //    7, 8, 9 }; 
      //  int[] array = {-1, 0,1, 1,1,2,3}; 
    int[] array = {1,1,1}; 

    int low = binarySearchFirst(array, 1); 
    int high = binarySearchLast(array, 1); 
    int total = (high >= low && low != -1 && high != -1) ? (high - low + 1): 0; 
    System.out.println("Total Frequency " + total); 
} 

    } 

Answer 7

Wie wäre dies für den sortierten Teil, mit O (log N) Zeitkomplexität suchen?

int count(int a[], int k, int l, int h) { 
    if (l>h) { 
    return 0; 
    } 
    int mid = (l+h)/2; 
    if (k > a[mid]) { 
    return count(a, k, mid+1, h); 
    } 
    else if (k < a[mid]) { 
    return count(a, k, l, mid-1); 
    } 
    else { 
    return count(a, k, mid+1, h) + count(a, k, l, mid-1) + 1; 
    } 
} 

Answer 8

#include<stdio.h> 
int binarysearch(int a[],int n,int k,bool searchfirst){ 
    int result=-1; 
    int low=0,high=n-1; 
    while(low<=high){ 
     int mid=(low+high)/2; 
     if(a[mid]==k) { 
       result=mid; 
      if(searchfirst) 
       high=mid-1; 
      else 
       low=mid+1; 
    } 
    else if(k<a[mid]) high=mid-1; 
    else low=mid+1; 
    } 
    return result; 
} 

int main(){ 
    int a[]={1,1,1,2,2,3,3,3,6,6,6,6,6,7,7}; 
    int n=sizeof(a)/sizeof(a[0]); 
    int x=6; 
    int firstindex=binarysearch(a,n,x,true); 
    printf("%d\n",firstindex); 
    if(firstindex==-1){ 
     printf("elment not found in the array:\n "); 
    } 
    else { 
     int lastindex=binarysearch(a,n,x,false); 
     printf("%d\n",lastindex); 
     printf("count is = %d", lastindex-firstindex+1); 
    } 

} 

Answer 9

Paket-Arrays;

/* * Bei einem sortierten Array ermitteln Sie, wie oft ein Element aufgetreten ist. * Binäre Suche O (LGN) * */

public class NumberOfN {

static int bSearchLeft(int[] arr, int start, int end, int n){ 

    while(start < end){ 

     int mid = (start + end)>>1; 
     if(arr[mid] < n){ 
      start = mid + 1; 
     }else{ 
      end = mid; 
     } 

    } 

    return end; 
} 

static int bSearchRight(int[] arr, int start, int end, int n){ 

    while(start < end){ 

     int mid = (start + end)>>1; 
     if(arr[mid] <= n){ 
      start = mid + 1; 
     }else{ 
      end = mid; 
     } 

    } 

    return end; 
} 

/** 
* @param args 
*/ 
public static void main(String[] args) { 

    int[] arr = new int[]{3,3,3,3}; 
    int n = 3; 
    int indexLeft = bSearchLeft(arr, 0, arr.length, n); 
    int indexRight = bSearchRight(arr, 0, arr.length, n); 
    System.out.println(indexLeft + " " +indexRight); 
    System.out.println("Number of occurences: " + (indexRight - indexLeft)); 
} 

}