Formatted question description: https://leetcode.ca/all/1287.html

1287. Element Appearing More Than 25% In Sorted Array (Easy)

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

 

Constraints:

  • 1 <= arr.length <= 10^4
  • 0 <= arr[i] <= 10^5

Related Topics:
Array

Solution 1.

// OJ: https://leetcode.com/problems/element-appearing-more-than-25-in-sorted-array/

// 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];
    }
};

Solution 2.

// OJ: https://leetcode.com/problems/element-appearing-more-than-25-in-sorted-array/

// 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/

// 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;
    }
};

Java

class Solution {
    public int findSpecialInteger(int[] arr) {
        int length = arr.length;
        Map<Integer, Integer> map = new HashMap<Integer, Integer>();
        for (int i = 0; i < length; i++) {
            int num = arr[i];
            int count = map.getOrDefault(num, 0);
            count++;
            if (count * 4 > length)
                return num;
            map.put(num, count);
        }
        return 0;
    }
}

All Problems

All Solutions