Moore vote, leetcode169, leetcode229

Moore voted

A preliminary understanding

Topics involved

LeetCode 169 - Majority Element

Description of algorithm

In a given array , Find out if there are more than n/2 The elements of . The title assumes that there must be an element that appears more than n/2 Time .

Ideas

Delete two different elements in the array each time , After traversing the array , The remaining elements must be more than n/2 Secondary elements .

• Define the candidate cand Give any value 、 Counter count Initialize to 0
• Traversal array
  • If count The value is 0, take cand Assign to the current value nums[i],count The assignment is 1
  • If count Values are not for 0, And current value nums[i] be equal to cand Value , be count Add one , otherwise count Minus one
• After traversal ,cand That is, the element

count Subtracting one can be understood as deleting the current element in the array nums[i] And a cand The elements of , When count Element is 0 It can be understood that all the preceding numbers have offset each other .

Code implementation

public int majorityElement(int[] nums) {
    
    int cand = 0;
    int count = 0;
    for (int i = 0; i< nums.length; ++i) {
    
        if (count == 0) {
    
            count = 1;
            cand = nums[i];
            continue;
        }
        if (cand == nums[i]) count++;
        else count--;
    }
    return cand;
}

Advanced

Topics involved

LeetCode 229 - Majority Element II

Ideas

The topic should be found to occur more than n/3 The elements of , But there is no guarantee that the element will exist .

Delete three different elements at a time , Last of all （ Two at most ） Must be the one who appears the most , But not necessarily greater than n/3 Time , You also need to iterate over whether the array count is greater than n/3. Thus more than n/k The elements of （ most k-1 individual ）.

• Define the candidate cand1 and cand2 Give any value 、 Counter count1 and count2 Initialize to 0
• Traverse the array to find possible elements for the first time
  • If the current value nums[i] be equal to cand1 or cand2 Value , Corresponding count1 or count2 Add one
  • If count1 or count2 The value is 0, take cand1 or cand2 Assign to the current value nums[i], Corresponding count assignment 1
  • otherwise count1 and count2 All minus one
• count1 and count2 The assignment is 0
• Traverse the array for the second time to determine whether the condition is met （ The frequency of occurrence is greater than n/3）
  • Judge nums[i] Whether or not cand1 or cand2 equal , Equal corresponds to count Add one
• Eventually greater than n/3 The element of the degree is the desired

Code implementation

public List<Integer> majorityElement(int[] nums) {
    
    List<Integer> result = new ArrayList<>();
    if (nums.length == 0) return result;
    int cand1 = 0;
    int cand2 = 0;
    int count1 = 0;
    int count2 = 0;
    for (int i = 0; i < nums.length; ++i) {
    
        if (cand1 == nums[i]) {
    
            count1++;
            continue;
        }
        if (cand2 == nums[i]) {
    
            count2++;
            continue;
        }
        if (count1 == 0) {
    
            count1 = 1;
            cand1 = nums[i];
            continue;
        }
        if (count2 == 0) {
    
            count2 = 1;
            cand2 = nums[i];
            continue;
        }
        count1--;
        count2--;
    }

    count1 = 0;
    count2 = 0;
    for (int i = 0; i < nums.length; ++i) {
    
        if (cand1 == nums[i]) count1++;
        else if (cand2 == nums[i]) count2++;
        // must do else if, because cand1 and cand2 It could be the same element 
    }
    if (count1 > (nums.length)/3) result.add(cand1);
    if (count2 > (nums.length)/3) result.add(cand2);

    return result;
}

Reference material

Moore voting algorithm ( Boyer-Moore Voting Algorithm)

LeetCode 0169 Majority Element

LeetCode 0229 Majority Element II Moore voted