Small knowledge, big challenge! This article is participating in the creation activity of “Essential Tips for Programmers”.

Most of the elements

Given an array of size N, find most of the elements. Most elements are those that occur more than ⌊ n/2 ⌋ in the array.

You can assume that the array is non-empty and that a given array always has most elements.

  • Example 1:

    Input: [3, 2, 3]

    Output: 3

  • Example 2:

    Input:,2,1,1,1,2,2 [2]

    Output: 2

[Advanced] :

An algorithm with time complexity O(n) and space complexity O(1) is designed to solve this problem.

Source: LeetCode

2. The Method of violence

// java
public static int majorityElement(int[] nums) {
    if(nums.length==1) {return nums[0];
    }
    // Use map to record the number of occurrences of each element
    // Returns the element when it appears more than half of the time
    // If not, return -1
    Map<Integer, Integer> map= new HashMap<>();
    for(int i = 0; i<nums.length; i++){if (map.containsKey(nums[i])){
            map.put(nums[i],map.get(nums[i])+1);
        }else{
            map.put(nums[i],1);
        }
        if(map.get(nums[i])>nums.length / 2) {returnnums[i]; }}return -1;
}
Copy the code

Moore voting

Moore vote: Find the number in a sequence of numbers that occurs more than 1/2 of the total number (assuming it must exist), so there can only be one number.

Core idea: one is equal to the other.

Each time two different numbers are selected from the sequence, they cancel each other out, and the last number or numbers that are the same is the number that occurs more than half the time.

public static int majorityElement(int[] nums){
    int major = nums[0];
    int count = 1;
    for (int i = 1; i < nums.length; i++) {
        if (count == 0) {
            // Reassign the value
            count++;
            major = nums[i];
        } else if (major == nums[i]) {
            // count is increment by 1
            count++;
        } else {
            // Kill one or both of uscount--; }}return major;
}
Copy the code

[Double pointer + Moore’s voting idea]

public static int majorityElement(int[] nums) {
    int left = 0,right = nums.length-1;
    // it is convenient to cancel heads and tails after sorting
    Arrays.sort(nums);
    // Double pointer + Moore voting idea
    while(left<=right){
        // If the first and last digits are different, cancel them out.
        // Add and subtract the first and last Pointers respectively
        if(nums[left]! =nums[right]) { left++; right--; }if(nums[left] == nums[right]){
            returnnums[left]; }}return -1;
}
Copy the code