Méthode efficace pour compter les occurrences d'une clé dans un tableau trié

Question

Cela a été demandé lors d'une interview Microsoft sur site.

Compter le nombre d'occurrences d'une clé donnée dans un tableau.

J'ai répondu à la recherche linéaire parce que les éléments peuvent être dispersés dans le tableau . Dites que la clé se trouve au début et à la fin. Nous avons donc besoin de scanner le tableau entier.

Ensuite, il a demandé si le tableau est trié? Pensé pendant un certain temps et dit que je vais utiliser la recherche linéaire à nouveau. Parce que les répétitions de la clé si présent peuvent être n'importe où dans le tableau. En tant qu'optimisation , j'ai aussi dit que si les premier et dernier éléments du tableau sont identiques, peut prendre la longueur du tableau comme réponse.

Mon analyse est-elle correcte dans les deux cas?

Exemple:

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

Si le tableau est non triés, oui, recherche linéaire d'un bout à l'autre est aussi bon qu'il obtient. Toutefois, si le tableau est trié, vous pouvez faire mieux que le temps linéaire en appliquant des techniques de recherche binaire ou d'interpolation.

Traitez le problème comme étant le même que "Trouvez le nombre X dans une liste triée" avec le détail ajouté de "puis scannez à gauche et à droite pour déterminer combien de fois X apparaît". La première partie, la recherche, est mieux faite avec une recherche binaire ou une interpolation dans la plupart des cas.

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

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

Answer 2

Oui, vous avez raison de tableau non trié, mais pour le tableau vous pouvez utiliser Sorted recherche binaire pour localiser une occurence de l'élément et une fois que l'on se trouve occurence analyse uniquement adjacente éléments jusqu'à ce que vous trouvez des discordances, puis arrêtez.

Answer 3

Pour le tableau non trié, nous ne pouvons pas faire grand-chose d'autre que la recherche linéaire.

Pour vous tableau trié pouvez le faire en utilisant O(logN) une recherche binaire légèrement modifiée:

• Trouver l'index de la première occurrence de key, appelez f.
• Trouvez l'index de la dernière occurrence de key, appelez le l.
• Si le key existe dans le tableau l-f+1 est la réponse.

trouver la première occurrence:

arr[i] est la première occurrence de key ssi

• arr[i] == keyet soit
  • i == 0 (il est le premier élément de la matrice) ou
  • arr[i-1] != key (ce n'est pas le premier élément du tableau et de l'élément à il reste est différent)

Vous pouvez modifier légèrement la recherche binaire pour trouver la première occurrence.
Dans une recherche binaire, vous terminez la recherche lorsque vous trouvez arr[mid] == key.
Modifier la condition telle que vous résiliez la recherche lorsque vous trouvez le premier événement au lieu de tout événement.

algorithme:

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 

De même, vous pouvez trouver la dernière occurrence.

Answer 4

Pour une fois, je proposerai une implémentation en C++.

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 utilise une recherche binaire, le résultat est équivalent à:

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

mais la mise en œuvre devrait en fait un peu plus rapide, même si tous sont en O (log N) (en termes de nombre de comparaison).

Answer 5

Vous pouvez utiliser la version récursive de recherche binaire

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) donne le nombre de touches

Answer 6

** Complexité = O (logn) où N est la taille du tableau

Arguments ** pour binarySearchXXXXX: **

1. int [] tableau est un tableau trié de longueur> = 1
2. int k: clé de recherche

**

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

Que diriez-vous cela pour la partie triée, avec O (logN) la complexité du temps?

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

réseaux de paquets;

/* * Étant donné un tableau trié, recherchez le nombre de fois qu'un élément s'est produit. * Recherche binaire 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)); 
} 

}