Given an integer array sorted in non-decreasing order, there is exactly one integer in the array that occurs more than 25% of the time.
Return that integer.
Example 1:
|
1 2 |
<strong>Input:</strong> arr = [1,2,2,6,6,6,6,7,10] <strong>Output:</strong> 6 |
Constraints:
1 <= arr.length <= 10^40 <= arr[i] <= 10^5
Solution 1: Linear Scan
if arr[i] == arr[i + len/4] => arr[i] is the special integer.
Time complexity: O(n)
Space complexity: O(1)
C++
|
1 2 3 4 5 6 7 8 9 10 |
// Author: Huahua class Solution { public: int findSpecialInteger(vector<int>& arr) { int s = arr.size() / 4; for (int i = 0; i + s < arr.size(); ++i) if (arr[i] == arr[i + s]) return arr[i]; return -1; } }; |
Solution 2: Binary Search
The answer must be one of (s[0], s[l/4], s[l/2], s[l*3/4])
Using binary search to find the range of each number, the one has more than 1/4 of total elements is the answer.
Time complexity: O(logn)
Space complexity: O(1)
C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 |
// Author: Huahua class Solution { public: int findSpecialInteger(vector<int>& arr) { const int s = arr.size() / 4; for (int i = 0; i < 4; ++i) { const int x = arr[i * s]; const auto [it1, it2] = equal_range(begin(arr), end(arr), x); if (it2 - it1 > s) return x; } return -1; } }; |
请尊重作者的劳动成果，转载请注明出处！花花保留对文章／视频的所有权利。
如果您喜欢这篇文章／视频，欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
Paypal
Venmo
huahualeetcode
huahualeetcode
微信打赏
Be First to Comment