Welcome to Subscribe On Youtube

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.

  • 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;
        }
    }
    
    ############
    
    class Solution {
        public int findSpecialInteger(int[] arr) {
            int n = arr.length;
            for (int i = 0; i < n; ++i) {
                if (arr[i] == arr[i + (n >> 2)]) {
                    return arr[i];
                }
            }
            return 0;
        }
    }
    
  • // 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];
        }
    };
    
  • class Solution:
        def findSpecialInteger(self, arr: List[int]) -> int:
            n = len(arr)
            for i, val in enumerate(arr):
                if val == arr[i + (n >> 2)]:
                    return val
            return 0
    
    ############
    
    # 1287. Element Appearing More Than 25% In Sorted Array
    # https://leetcode.com/problems/element-appearing-more-than-25-in-sorted-array/
    
    class Solution:
        def findSpecialInteger(self, arr: List[int]) -> int:
            n = len(arr)
            m = len(arr) // 4
            
            for i in range(n-m+1):
                if arr[i] == arr[i+m]:
                    return arr[i]
    
  • func findSpecialInteger(arr []int) int {
    	n := len(arr)
    	for i, val := range arr {
    		if val == arr[i+(n>>2)] {
    			return val
    		}
    	}
    	return 0
    }
    
  • /**
     * @param {number[]} arr
     * @return {number}
     */
    var findSpecialInteger = function (arr) {
        const n = arr.length;
        for (let i = 0; i < n; ++i) {
            if (arr[i] == arr[i + (n >> 2)]) {
                return arr[i];
            }
        }
        return 0;
    };
    
    
  • class Solution {
        /**
         * @param Integer[] $arr
         * @return Integer
         */
        function findSpecialInteger($arr) {
            $len = count($arr);
            for ($i = 0; $i < $len; $i++) {
                if ($arr[$i] == $arr[$i + ($len >> 2)]) return $arr[$i];
            }
            return -1;
        }
    }
    

All Problems

All Solutions