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