1287. Element Appearing More Than 25% In Sorted Array

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

Rust Solution

struct Solution;

impl Solution {
    fn find_special_integer(arr: Vec<i32>) -> i32 {
        let n = arr.len();
        let t = n / 4;
        for i in 0..n - t {
            if arr[i] == arr[i + t] {
                return arr[i];
            }
        }
        0
    }
}

#[test]
fn test() {
    let arr = vec![1, 2, 2, 6, 6, 6, 6, 7, 10];
    assert_eq!(Solution::find_special_integer(arr), 6);
}

Having problems with this solution? Click here to submit an issue on github.