Leetcode_1287_Element Appearing More Than 25% In Sorted Array

[lihe]

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

// 1ms 39.3MB
class Solution {
    public int findSpecialInteger(int[] arr) {
        int result = arr[0];
        int i = 0;
        int cnt = 0;
        while (i < arr.length){
            cnt = 0;
            while (arr[i] == result){
                cnt ++;
                if(cnt >= arr.length / 4 + 1){
                    return result;
                }
                i++;
            }
            result = arr[i];
        }
        return result;
    }
}

// 11ms 39.2MB
class Solution {
    public int findSpecialInteger(int[] arr) {
        int[] list = new int[100000];
        int result = 0;
        for(int i = 0; i < arr.length; i++){
            list[arr[i]]++;
        }
        for(int i = 0; i < list.length; i++){
            if(list[i] >= (int)Math.ceil((double)arr.length / 4)){
                result = i;
            }
        }
        return result;
    }
}