[leetcode] sword finger offer 39 Numbers that appear more than half of the time in the array

There is a number in an array that appears more than half the length of the array , Please find out the number .

You can assume that the array is not empty , And there are always many elements in a given array .

Example 1:

Input : [1, 2, 3, 2, 2, 2, 5, 4, 2]
Output : 2

Limit ：

1 <= The length of the array <= 50000

Answer 1 ：

	/** *  The finger of the sword  Offer 39.  A number that appears more than half the times in an array  */
    public int majorityElement(int[] nums) {
    
        //  Because the mode occurs more than half the length of the array , Then the midpoint element after sorting must be mode 
        Arrays.sort(nums);
        return nums[nums.length / 2];
    }

Explanation 2 ：

    /** *  The finger of the sword  Offer 39.  A number that appears more than half the times in an array  */
    public int majorityElement(int[] nums) {
    
        /* *  Use a hash table to count the number of occurrences of each element , Returns the element with the most occurrences  *  Optimize ： In order to avoid traversing the hash table, find the most frequent  key, *  Maintain the most frequent elements in the process of traversing the array  res  And the number of occurrences  maxTimes, *  initialization  res  and  maxTimes  For the first element in the array  */
        Map<Integer, Integer> integerMap = new HashMap<>();
        int maxTimes = 1;
        int res = nums[0];
        
        for (int num : nums) {
    
            //  The current element appears for the first time 
            if (!integerMap.containsKey(num)) {
    
                integerMap.put(num, 1);
            } else {
    
                int curNumTimes = integerMap.get(num) + 1;
                if (curNumTimes > maxTimes) {
    
                    maxTimes = curNumTimes;
                    res = num;
                }
                integerMap.put(num, curNumTimes);
            }
        }
        return res;
    }

Answer 3 ：

/** *  The finger of the sword  Offer 39.  A number that appears more than half the times in an array  */
    public int majorityElement(int[] nums) {
    
        /* *  Moore voting ： The value of Jizhong is  +1, The unusual value is  -1, Then the sum of all elements in the array must be greater than  0 *  In the process of traversing the array, if the number of votes  votes  be equal to  0  Then assume that the current element is the mode  mode, *  If the current element is equal to mode  mode  The number of votes  votes++, otherwise  votes--, Then the final assumed number must be the mode  */
        int votes = 0;
        int mode = 0;
        for (int num : nums) {
    
            if (votes == 0) {
    
                mode = num;
            }
            votes += (num == mode ? 1 : -1);
        }
        return mode;
    }