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:
Input: arr = [1,2,2,6,6,6,6,7,10] Output: 6
Example 2:
Input: arr = [1,1] Output: 1
Constraints:
1 <= arr.length <= 104
0 <= arr[i] <= 105
Companies: Amazon, Adobe, Facebook, Google
Related Topics:
Array
Hints:
- Divide the array in four parts [1 - 25%] [25 - 50 %] [50 - 75 %] [75% - 100%]
- The answer should be in one of the ends of the intervals.
- In order to check which is element is the answer we can count the frequency with binarySearch.
// OJ: https://leetcode.com/problems/element-appearing-more-than-25-in-sorted-array/
// Author: github.com/lzl124631x
// Time: O(N)
// Space: O(1)
class Solution {
public:
int findSpecialInteger(vector<int>& A) {
int start = 0, N = A.size();
for (int i = 1; i < N; ) {
while (i < N && A[i] == A[start]) ++i;
if (i - start > N / 4) return A[start];
start = i;
}
return A[0];
}
};
// OJ: https://leetcode.com/problems/element-appearing-more-than-25-in-sorted-array/
// Author: github.com/lzl124631x
// Time: O(N)
// Space: O(1)
class Solution {
public:
int findSpecialInteger(vector<int>& A) {
int N = A.size(), t = N / 4;
for (int i = 0; i < N - t; ++i) {
if (A[i] == A[i + t]) return A[i];
}
return -1;
}
};
// OJ: https://leetcode.com/problems/element-appearing-more-than-25-in-sorted-array/
// Author: github.com/lzl124631x
// Time: O(logN)
// Space: O(1)
class Solution {
public:
int findSpecialInteger(vector<int>& A) {
int N = A.size(), sizes[3] = { N / 4, N / 2, N * 3 / 4 };
for (int i : sizes) {
if (upper_bound(begin(A), end(A), A[i]) - lower_bound(begin(A), end(A), A[i]) > N / 4) return A[i];
}
return -1;
}
};