Description
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 <= 1040 <= arr[i] <= 105
Solutions
Solution 1: Traversal
We traverse the array arr from the beginning. For each element arr[i], we check if arr[i] is equal to arr[i + \left\lfloor n⁄4 \right\rfloor], where n is the length of the array. If they are equal, then arr[i] is the element we are looking for, and we return it directly.
The time complexity is O(n), where n is the length of the array arr. The space complexity is O(1).
PythonJavaC++GoTypeScriptJavaScriptPHP
class Solution:
def findSpecialInteger(self, arr: List[int]) -> int:
n = len(arr)
for i, x in enumerate(arr):
if x == arr[(i + (n >> 2))]:
return x(code-box)
class Solution {
public int findSpecialInteger(int[] arr) {
for (int i = 0;; ++i) {
if (arr[i] == (arr[i + (arr.length >> 2)])) {
return arr[i];
}
}
}
}(code-box)
class Solution {
public:
int findSpecialInteger(vector<int>& arr) {
for (int i = 0;; ++i) {
if (arr[i] == (arr[i + (arr.size() >> 2)])) {
return arr[i];
}
}
}
};(code-box)
func findSpecialInteger(arr []int) int {
for i := 0; ; i++ {
if arr[i] == arr[i+len(arr)/4] {
return arr[i]
}
}
}(code-box)
function findSpecialInteger(arr: number[]): number {
const n = arr.length;
for (let i = 0; ; ++i) {
if (arr[i] === arr[i + (n >> 2)]) {
return arr[i];
}
}
}(code-box)
/**
* @param {number[]} arr
* @return {number}
*/
var findSpecialInteger = function (arr) {
const n = arr.length;
for (let i = 0; ; ++i) {
if (arr[i] === arr[i + (n >> 2)]) {
return arr[i];
}
}
};(code-box)
class Solution {
/**
* @param Integer[] $arr
* @return Integer
*/
function findSpecialInteger($arr) {
$n = count($arr);
for ($i = 0; ; ++$i) {
if ($arr[$i] == $arr[$i + ($n >> 2)]) {
return $arr[$i];
}
}
}
}(code-box)
