Majority Vote总结

Majority Element题型是找一个数组中超过n/k的majority元素,使用的算法是Majority Vote。
原理就是对于每一个Majority Element都设置一个count:1.如果选中的num与Majority Element相等,对应的count++ 2.如果所有的Majority Element没有与num相等的,那么去检查有没有count为0,如果有,将这个Majority Element设置为num并将count设为1 3.如果以上都不符合,那么所有count–

所以我们看到程序中都是用的if,else if,也就是说有符合条件的情况,对于这个num的判断就结束了

  1. Majority Element

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    /*
    169. Majority Element
    Easy

    2074

    181

    Favorite

    Share
    Given an array of size n, find the majority element. The majority element is the element that appears more than ⌊ n/2 ⌋ times.

    You may assume that the array is non-empty and the majority element always exist in the array.

    Example 1:

    Input: [3,2,3]
    Output: 3
    Example 2:

    Input: [2,2,1,1,1,2,2]
    Output: 2
    */
    class Solution {
    public int majorityElement(int[] nums) {
    int majority = 0;
    int count = 0;
    for(int i = 0;i<=nums.length-1;i++){
    if(nums[i]==majority){
    count++;
    }
    else if(count==0){
    majority = nums[i];
    count++;
    }
    else {
    count--;
    }
    }
    return majority;

    }
    }
  2. Majority Element II

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    75
    76
    77
    78
    /*
    229. Majority Element II
    Medium

    1081

    125

    Favorite

    Share
    Given an integer array of size n, find all elements that appear more than ⌊ n/3 ⌋ times.

    Note: The algorithm should run in linear time and in O(1) space.

    Example 1:

    Input: [3,2,3]
    Output: [3]
    Example 2:

    Input: [1,1,1,3,3,2,2,2]
    Output: [1,2]
    */
    class Solution {
    public List<Integer> majorityElement(int[] nums) {
    int majority1 = 0;
    int majority2 = 0;
    int count1 = 0;
    int count2 = 0;
    for(int i = 0;i<=nums.length-1;i++){
    //先判断是否有Majority等于nums[i]
    if(nums[i] == majority1){
    count1++;
    }
    else if(nums[i] == majority2){
    count2++;
    }
    //再判断是否有count为0
    //先后顺序不能变,不能先判断count是否为0,因为可能有一个majority的count是0,但另一个不是0,那么他还可能等于nums[i]
    else if(count1==0){
    majority1 = nums[i];
    count1++;
    }
    else if(count2==0){
    majority2 = nums[i];
    count2++;
    }
    //都不符合的话count都减1
    else {
    count1--;
    count2--;
    }
    }

    List<Integer> l = new LinkedList<>();

    count1 = 0;
    count2 = 0;
    for(int num:nums){
    if(num==majority1){
    count1++;
    }
    else if(num==majority2){
    count2++;
    }
    }

    if(count1>nums.length/3){
    l.add(majority1);
    }
    if(count2>nums.length/3){
    l.add(majority2);
    }

    return l;
    }
    }