Эффективный способ подсчета вхождений ключа в отсортированный массив
Об этом было задано в интервью Microsoft на сайте.
Подсчитайте количество вхождений заданного ключа в массиве.
Я ответил на линейный поиск, потому что элементы могут быть рассеяны в
массив. Скажем, ключ найден в начале и в конце. Итак, мы
необходимо сканировать весь массив.
Затем он спросил, что, если массив отсортирован?
Подумал какое-то время и сказал, что снова буду использовать линейный поиск. Поскольку
повторения ключа, если они имеются, могут быть в любом месте массива. Как
оптимизация Я также сказал, что если первый и последний элементы массива одинаковы, вы
может принимать длину массива в качестве ответа.
Является ли мой анализ правильным в обоих случаях?
Пример:
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
Ответы
Ответ 1
Для несортированного массива мы не можем сделать ничего, кроме линейного поиска.
Для отсортированного массива вы можете сделать это в O(logN)
с помощью слегка измененного двоичного поиска:
- Найдите индекс первого появления
key
, назовите его f
.
- Найдите индекс последнего вхождения
key
, назовите его l
.
- Если
key
существует в массиве l-f+1
это ответ.
Поиск первого вхождения:
arr[i]
- первое вхождение key
iff
-
arr[i] == key
и
-
i == 0
(это первый элемент
массив) или
-
arr[i-1] != key
(это не первый
элемент массива и элемента
он остался разным)
Вы можете немного изменить бинарный поиск, чтобы найти первое вхождение.
В двоичном поиске вы прекратите поиск, когда найдете arr[mid] == key
.
Измените условие, при котором вы прекратите поиск, когда найдете first вместо любого.
Алгоритм:
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
Аналогично вы можете найти последнее вхождение.
Ответ 2
В один раз я предлагаю реализацию в С++.
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
использует двоичный поиск, результат эквивалентен:
std::make_pair(std::lower_bound(vec.begin(), vec.end(), key),
std::upper_bound(vec.begin(), vec.end(), key);
но реализация должна сделать его немного быстрее, хотя все они находятся в O (log N) (с точки зрения количества сравнения).
Ответ 3
#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);
}
}
Ответ 4
Вы можете использовать рекурсивную версию двоичного поиска
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)
задает количество клавиш
Ответ 5
**
Сложность времени= O (lg N), где N - размер массива
** Аргументы для binarySearchXXXXX: **
- int [] array - отсортированный массив длиной >= 1
- int k: ключ для поиска
**
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);
}
}
Ответ 6
Как насчет этого для отсортированной части, с временной сложностью O (logN)?
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;
}
}
Ответ 7
массивы пакетов;
/*
* Учитывая отсортированный массив, найдите количество раз, когда произошел элемент.
* Двоичный поиск O (lgn)
* */
открытый класс 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));
}
}
Ответ 8
Мы можем решить эту проблему, используя как линейный, так и бинарный поиск. Но линейный поиск будет O (n). Двоичный поиск даст O (Logn). Следовательно лучше использовать бинарный поиск. Полная программа:
public class Test4 {
public static void main(String[] args) {
int a[] = {1, 2, 2, 3, 3, 3, 6,6,6,6,6,66,7};
int x = 6;
System.out.println(fix(a,x));
}
private static int fix(int[] a, int x) {
int res = 0 ;
for (int i = 0; i < a.length; i++) {
int ch = a[i];
if(x == ch) {res++ ;}
}
return res;
}
}
Есть еще один вопрос: "1-е и последнее вхождение заданного числа в отсортированный массив".
class Occurence1 {
public static void findFirstAndLast(int a[], int x) {
int first = -1, last = -1;
for (int i = 0; i < a.length; i++) {
if (x == a[i]) {
if (first == -1) {
first = i;
}
// update last
last = i;
} // if
} // for
if (first != -1) {
System.out.println("First Occurrence = " + first);
System.out.println("Last Occurrence = " + last);
}
}// end1
public static void main(String[] args) {
int arr[] = { 1, 2, 2, 2, 2, 3, 4, 7, 8, 8 };
int x = 8;
findFirstAndLast(arr, x);
}
}
В Python:
def findFirstAndLast(a, x):
first = -1 ; last = -1
for i in range(len(a)) :
if(x == a[i]):
if(first == -1):first = i
# update last if the first contains oter value than -1
last = i
if(first != -1):
print("first => ",first)
print("last =>", last)
a = [1, 2, 3,4, 5, 6, 7, 8, 1, 10, 10]
x = 10
findFirstAndLast(a, x)
Ответ 9
Если массив несортирован, да, линейный поиск с одного конца на другой так же хорош, как и он.
Однако, если массив отсортирован, вы можете сделать лучше, чем линейное время, применяя методы поиска в двоичном или интерполяционном режиме.
Рассматривайте проблему так же, как "Найти число X в отсортированном списке" с добавленной деталью "затем сканируйте влево и вправо, чтобы определить, сколько раз появляется X". Первая часть, поиск, лучше всего делать с бинарным или интерполяционным поиском в большинстве случаев.
http://en.wikipedia.org/wiki/Interpolation_search
http://en.wikipedia.org/wiki/Binary_search
Ответ 10
Да, вы правы для несортированного массива, но для отсортированного массива вы можете использовать бинарный поиск, чтобы найти одно из элементов этого элемента, и как только это обнаружение обнаружено, только сканируйте соседние элементы, пока не найдете несоответствия, а затем остановитесь.