• 一个数的重复次数超过数组长度的一半，每次将两个不相同的数删除，最终剩下的就是要找的数

      1. public int majorityElement(int[] nums){
      2.   int count = 0;
      3.   int num = nums[0];
      4.   for(int i=1;i<nums.length;i++){
      5.       if(nums[i] != num){
      6.           count--;
      7.           if(count < 0){
      8.               count = 0;
      9.               num = nums[i];
      10.           }
      11.       }else{
      12.           count++;
      13.       }
      14.   }
      15.   return num;
      16. }

    • 给定一个大小为 n 的整数数组，找出其中所有出现超过 ⌊ n/3 ⌋ 次的元素

      • 答案至多两个

        1. class Solution {
        2. public List<Integer> majorityElement(int[] nums) {
        3.    int element1 = 0;
        4.    int element2 = 0;
        5.    int vote1 = 0;
        6.    int vote2 = 0;
        8.    for (int num : nums) {
        9.        if (vote1 > 0 && num == element1) { //如果该元素为第一个元素，则计数加1
        10.            vote1++;
        11.        } else if (vote2 > 0 && num == element2) { //如果该元素为第二个元素，则计数加1
        12.            vote2++;
        13.        } else if (vote1 == 0) { // 选择第一个元素
        14.            element1 = num;
        15.            vote1++;
        16.        } else if (vote2 == 0) { // 选择第二个元素
        17.            element2 = num;
        18.            vote2++;
        19.        } else { //如果三个元素均不相同，则相互抵消1次
        20.            vote1--;
        21.            vote2--;
        22.        }
        23.    }
        25.    int cnt1 = 0;
        26.    int cnt2 = 0;
        27.    for (int num : nums) {
        28.        if (vote1 > 0 && num == element1) {
        29.            cnt1++;
        30.        }
        31.        if (vote2 > 0 && num == element2) {
        32.            cnt2++;
        33.        }
        34.    }
        35.    // 检测元素出现的次数是否满足要求
        36.    List<Integer> ans = new ArrayList<>();
        37.    if (vote1 > 0 && cnt1 > nums.length / 3) {
        38.        ans.add(element1);
        39.    }
        40.    if (vote2 > 0 && cnt2 > nums.length / 3) {
        41.        ans.add(element2);
        42.    }
        43.    return ans;
        44. }
        45. }