[LeetCode/Easy] 1287. Element Appearing More Than 25% In Sorted Array

1. Input

1) int[] arr

- arr는 오름차순으로 정렬되어있다.

 

2. Output

1) arr의 25%를 넘게 차지하고 있는 요소를 반환

 

3. Constraint

1) 1 <= arr.length <= 10^4

2) 0 <= arr[i] <= 10^5

 

4. Example

Input: arr = [1,2,2,6,6,6,6,7,10] -> Output: 6

Input: arr = [1,1] -> Output: 1

 

5. Code

1) 첫 코드(2023/06/08)

class Solution {
    public int findSpecialInteger(int[] arr) {
        HashMap<Integer,Integer> m = new HashMap<>();
        for(int i : arr)
            m.put(i, m.getOrDefault(i,0)+1);
        int ans = 0;
        for(int i : m.keySet())
            if(m.get(i)>arr.length/4.0){
                ans = i; break;
            }
        return ans;
    }
}

- 24%, 10%

 

2) 다시 풀어본 코드(2023/06/08)

class Solution {
    public int findSpecialInteger(int[] arr) {
        int ans = 0;
        for(int i=0 ; i<arr.length ; i++){
            int j = i+1;
            while(j<arr.length && arr[i]==arr[j]) j++;
            if(j-i>arr.length/4.0) {
                ans = arr[i]; break;
            }
            i = j-1;
        }
        return ans;
    }
}

- 59%, 50%