2780. Minimum Index of a Valid Split - Medium

前往題目

想法

• 先找出最多的那個元素，然後迭代的時候再算其元素在左邊以及右邊各有多少

思路

就和我的想法一樣，不過最後我忘了除二或乘二去正確判斷超過半數

Code

class Solution {
    public int minimumIndex(List<Integer> nums) {
        int[] dominant = new int[]{0, 0};

        // Number -> count
        HashMap<Integer, Integer> map = new HashMap();

        // Find the dominant element
        for (int num : nums) {
            map.put(num, 1 + map.getOrDefault(num, 0));

            // Update the dominant element
            if (dominant[1] < map.get(num)) {
                dominant[0] = num;
                dominant[1] = map.get(num);
            }
        }

        int currentDominantCount = 0;
        for (int i = 0; i < nums.size(); ++i) {
            // When encounter dominant value
            if (nums.get(i) == dominant[0]) {
                ++currentDominantCount;
            }

            int secondDominantCount = dominant[1] - currentDominantCount;

            // When dominant dominates
            // Times 2 or divided by two ((i + 1) / 2) || ((nums.size() - i - 1) / 2) are both valid, since the point is to check the elements are more than half of the range
            if (currentDominantCount * 2 > (i + 1) && secondDominantCount * 2 > (nums.size() - i - 1)) {
                return i;
            }
        }

        return -1;
    }
}