# 給定范圍內的最大出現次數 > 原文： [https://www.geeksforgeeks.org/maximum-occurrence-given-range/](https://www.geeksforgeeks.org/maximum-occurrence-given-range/) 以非降序給出`n`個整數數組。 查找給定范圍內最頻繁出現的值的數量。 例子： ``` Input : arr[] = {-5, -5, 2, 2, 2, 2, 3, 7, 7, 7} Query 1: start = 0, end = 9 Query 2: start = 4, end = 9 Output : 4 3 Explanation: Query 1: '2' occurred the most number of times with a frequency of 4 within given range. Query 2: '7' occurred the most number of times with a frequency of 3 within given range. ``` 段樹可用于有效解決此問題。 有關分段樹 的實現，請參見此處的[。 該問題背后的關鍵思想是給定數組的順序為非遞減順序，這意味著所有出現的數字都連續放置在 數組，因為數組是按排序順序排列的。 可以構建一個分段樹，其中每個節點將存儲其各自范圍`[i, j]`的最大計數。 為此，我們將構建頻率數組并在該數組上調用 RMQ（范圍最大查詢）。 例如](https://www.geeksforgeeks.org/segment-tree-set-1-range-minimum-query/) ``` arr[] = {-5, -5, 2, 2, 2, 2, 3, 7, 7, 7} freq_arr[] = {2, 2, 4, 4, 4, 4, 1, 3, 3, 3} where, freq_arr[i] = frequency(arr[i]) ``` 現在要考慮兩種情況： **情況 1：給定范圍的索引`i`和`j`處的數字值相同，即`arr[i] = arr[j]`。** 解決這種情況非常容易。 由于`arr[i] = arr[j]`，因此這些索引之間的所有數字都是相同的（因為數組是非遞減的）。 因此，這種情況的答案就是簡單地計算`i`和`j`（包括兩個端點）之間的所有數字，即`j – i + 1` ``` arr[] = {-5, -5, 2, 2, 2, 2, 3, 7, 7, 7} if the given query range is [3, 5], answer would be (5 - 3 + 1) = 3, as 2 occurs 3 times within given range ``` **情況 2：給定范圍的索引`i`和`i`處的數字值不同，即`arr[i] != arr[j]`。** 如果`arr[i] != arr[j]`，則存在一個索引`k`，其中`arr[i] = arr[k]`，而`arr[i] != arr[k +1]`。 這可能是部分重疊的情況，其中特定數字的某些出現在給定范圍的最左部分，而某些恰好在范圍開始之前。 在這里簡單地調用 RMQ 將導致錯誤的答案。例如： ``` arr[] = {-5, -5, 2, 2, 2, 2, 3, 7, 7, 7} freq_arr[] = {2, 2, 4, 4, 4, 4, 1, 3, 3, 3} if the given query is [4, 9], calling RMQ on freq_arr[] will give us 4 as answer which is incorrect as some occurrences of 2 are lying outside the range. Correct answer is 3. ``` 在給定范圍的最右側可能會發生類似情況，其中某些特定數字出現在該范圍內，而某些出現在該范圍結束之后。 因此，在這種情況下，在給定范圍內，我們必須計算直到索引`i`的最左邊相同數字，以及從索引`j`到范圍末尾的最右邊相同數字。 然后在索引`i`和`j`之間調用 RMQ（范圍最大查詢），并取這三個值中的最大值。例如： ``` arr[] = {-5, -5, 2, 2, 2, 2, 3, 7, 7, 7} freq_arr[] = {2, 2, 4, 4, 4, 4, 1, 3, 3, 3} if the given query is [4, 7], counting leftmost same numbers i.e 2 which occurs 2 times inside the range and rightmost same numbers i.e. 3 which occur only 1 time and RMQ on [6, 6] is 1\. Hence maximum would be 2. ``` 下面是上述方法的實現 ``` // C++ Program to find the occurrence // of the most frequent number within // a given range #include <bits/stdc++.h> using namespace std; // A utility function to get the middle index // from corner indexes. int getMid(int s, int e) { return s + (e - s) / 2; } /*? A recursive function to get the maximum value in ????a given range? of array indexes. The following ????are parameters for this function. ????st??? --> Pointer to segment tree ????index --> Index of current node in the segment? ??????????????tree. Initially 0 is passed as root is ??????????????always at index 0 ????ss & se? --> Starting and ending indexes of the? ?????????????????segment represented by current node, ??????????????????i.e., st[index] ????qs & qe? --> Starting and ending indexes of query? ?????????????????range */ int RMQUtil(int* st, int ss, int se, int qs, int qe,? ??????????????????????????????????????????int index) { ????// If segment of this node is a part of given range, ????//? then return the min of the segment ????if (qs <= ss && qe >= se) ????????return st[index]; ????// If segment of this node is outside the ????// given range ????if (se < qs || ss > qe) ????????return 0; ????// If a part of this segment overlaps? ????// with the given range ????int mid = getMid(ss, se); ????return max(RMQUtil(st, ss, mid, qs, qe, 2 * index + 1), ???????????????RMQUtil(st, mid + 1, se, qs, qe, 2 * index + 2)); } // Return minimum of elements in range from // index qs (query start) to // qe (query end).? It mainly uses RMQUtil() int RMQ(int* st, int n, int qs, int qe) { ????// Check for erroneous input values ????if (qs < 0 || qe > n - 1 || qs > qe) { ????????printf("Invalid Input"); ????????return -1; ????} ????return RMQUtil(st, 0, n - 1, qs, qe, 0); } // A recursive function that constructs Segment Tree // for array[ss..se]. si is index of current node in // segment tree st int constructSTUtil(int arr[], int ss, int se, int* st,? ???????????????????????????????????????????????int si) { ????// If there is one element in array, store it in ????//? current node of segment tree and return ????if (ss == se) { ????????st[si] = arr[ss]; ????????return arr[ss]; ????} ????// If there are more than one elements, then? ????// recur for left and right subtrees and store? ????// the minimum of two values in this node ????int mid = getMid(ss, se); ????st[si] = max(constructSTUtil(arr, ss, mid, st, si * 2 + 1), ?????????????????constructSTUtil(arr, mid + 1, se, st, si * 2 + 2)); ????return st[si]; } /* Function to construct segment tree from given? ???array. This function allocates memory for segment ???tree and calls constructSTUtil() to fill the? ???allocated memory */ int* constructST(int arr[], int n) { ????// Allocate memory for segment tree ????// Height of segment tree ????int x = (int)(ceil(log2(n))); ????// Maximum size of segment tree ????int max_size = 2 * (int)pow(2, x) - 1; ????int* st = new int[max_size]; ????// Fill the allocated memory st ????constructSTUtil(arr, 0, n - 1, st, 0); ????// Return the constructed segment tree ????return st; } int maximumOccurrence(int arr[], int n, int qs, int qe) { ????// Declaring a frequency array ????int freq_arr[n + 1]; ????// Counting frequencies of all array elements. ????unordered_map<int, int> cnt; ????for (int i = 0; i < n; i++) ????????cnt[arr[i]]++;? ????// Creating frequency array by replacing the? ????// number in array to the number of times it? ????// has appeared in the array ????for (int i = 0; i < n; i++) ????????freq_arr[i] = cnt[arr[i]]; ????// Build segment tree from this frequency array ????int* st = constructST(freq_arr, n); ????int maxOcc; // to store the answer ????// Case 1: numbers are same at the starting? ????// and ending index of the query ????if (arr[qs] == arr[qe]) ????????maxOcc = (qe - qs + 1); ????// Case 2: numbers are different ????else { ????????int leftmost_same = 0, righmost_same = 0; ????????// Partial Overlap Case of a number with some ????????// occurrences lying inside the leftmost ????????//? part of the range and some just before the ????????// range starts ????????while (qs > 0 && qs <= qe && arr[qs] == arr[qs - 1]) { ????????????qs++; ????????????leftmost_same++; ????????} ????????// Partial Overlap Case of a number with some? ????????// occurrences lying inside the rightmost part of? ????????// the range and some just after the range ends ????????while (qe >= qs && qe < n - 1 && arr[qe] == arr[qe + 1]) { ????????????qe--; ????????????righmost_same++; ????????} ????????// Taking maximum of all three ????????maxOcc = max({leftmost_same, righmost_same,? ????????????????????????????????RMQ(st, n, qs, qe)}); ????} ????return maxOcc; } // Driver Code int main() { ????int arr[] = { -5, -5, 2, 2, 2, 2, 3, 7, 7, 7 }; ????int n = sizeof(arr) / sizeof(arr[0]); ????int qs = 0; // Starting index of query range ????int qe = 9; // Ending index of query range ????// Print occurrence of most frequent number? ????// within given range ????cout << "Maximum Occurrence in range is = "? ?????????<< maximumOccurrence(arr, n, qs, qe) << endl; ????qs = 4; // Starting index of query range ????qe = 9; // Ending index of query range ????// Print occurrence of most frequent number ????// within given range ????cout << "Maximum Occurrence in range is = "? ?????????<< maximumOccurrence(arr, n, qs, qe) << endl; ????return 0; } ``` **輸出**： ``` Maximum Occurrence in range is = 4 Maximum Occurrence in range is = 3 ``` **進一步優化**：對于部分重疊的情況，我們必須運行一個循環以計算兩側相同數字的計數。 為了避免該循環并在`O(1)`中執行此操作，我們可以將每個數字的首次出現的索引存儲在給定數組中，因此通過進行一些預計算，可以在`O(1)`中找到所需的計數。 **時間復雜度**： 樹構建的時間復雜度為`O(n)`。 查詢的時間復雜度為`O(log n)`。 * * * * * *