更好的算法可以找到一個元素的重複次數，給定一個重複了任何no的元素的排序數組。時間

Question

我試過對給定元素進行二進制搜索，並向左向右遍歷它，直到它獲得大於或小於它的元素爲止，但是如果所有元素都相同，它將一直持續到O（n）時間複雜度。有更好的算法嗎？

Answer 1

您可以使用二進制搜索來查找範圍的下限（和/或上限），並執行二進制搜索以查找下限，以及元素範圍的上限或下限一個比你關心的還要大。

編輯：我發現的下界的大部分代碼是（我相信）比真正必要的更復雜一點。

int *find(int *left, int *right, int val) { 
    assert(left<right); 
    while (left < right) { 
     int *middle = left + (right - left)/2; 
     if (*middle < val) 
      left = middle + 1; 
     else 
      right = middle; 
    } 
    return left; 
} 

Answer 2

做兩個二進制搜索：

在第一個搜索你選擇的左半部分，如果中間元素等於尋求元素。

在第二個搜索中，如果中間元素等於搜索元素，則選擇右半部分。

示例代碼在Java中：

class Test { 

    public static int findElem(int[] arr, int elem, int l, int h,boolean first) { 
     if (h - l <= 1) 
      return first ? (arr[l] == elem ? l : h) : (arr[h] == elem ? h : l); 

     int m = l + (h - l)/2; 

     if (arr[m] < elem || (arr[m] == elem && !first)) 
      return findElem(arr, elem, m, h, first); 

     return findElem(arr, elem, l, m, first); 
    } 

    public static int findElem(int[] arr, int elem, boolean first) { 
     return findElem(arr, elem, 0, arr.length, first); 
    } 

    public static void main(String[] args) { 
     int[] arr = { 0, 1, 2, 2, 2, 3, 3, 4, 4, 5 }; 

     int elem = 2; 

     System.out.println("First index: " + findElem(arr, elem, true)); 
     System.out.println("Last index : " + findElem(arr, elem, false)); 
    } 
} 

Answer 3

您應該二進制搜索第一個和你匹配序列的最後一個元素。如果您使用的是C++，那麼在STL中有像lower_bound和upper_bound這樣的函數可以讓您這樣做。否則，這是對算法的簡單修改。

或者，你可以使用3個二進制搜索：

1. 爲匹配您的價值
2. 二進制搜索自己範圍的左側任意元素的二進制搜索
3. 爲右側二進制搜索範圍

但是，能夠做到最後2意味着您已經實現了第一個解決方案（通過查找下限/上限）

Answer 4

如果您打算多次執行此操作，則可以創建一個散列表，其中元素值爲鍵，第一個和最後一個元素的索引爲值。

讀取數據以創建哈希表是O（n）操作，但查找索引接近O（1）操作。

Answer 5

考慮你有一個排序數組a of n類型的元素T。那麼對於某些元素x你可以找到它的重複次數爲：

T* ub = upper_bound(a, a + n, x); 
int answer = ub - lower_bound(a, ub, x); 

的複雜性顯然是O(logn)。當所有元素相同或者a中沒有元素x時，upper_bound將返回到a+n和lower_bound將在整個區間工作，這將在這些最壞情況下進行2 * logn迭代。