Java代码找出数组中出现次数大于三分之一次的数

Java代码找出数组中出现次数大于三分之一次的数

问题描述： 给定一个整数数组，找出数组中出现次数大于三分之一次的数。

示例： 输入：[1,2,3,1,3,2,1,2,9,1,2,2] 输出：[1, 2]

代码实现：

public class Main {
    public static void main(String[] args) {
        int[] nums = {1,2,3,1,3,2,1,2,9,1,2,2};
        List<Integer> res = majorityElement(nums);
        System.out.println(res);
    }

    public static List<Integer> majorityElement(int[] nums) {
        List<Integer> res = new ArrayList<>();
        int candidate1 = 0, candidate2 = 0, count1 = 0, count2 = 0;
        for (int num : nums) {
            if (num == candidate1) {
                count1++;
            } else if (num == candidate2) {
                count2++;
            } else if (count1 == 0) {
                candidate1 = num;
                count1++;
            } else if (count2 == 0) {
                candidate2 = num;
                count2++;
            } else {
                count1--;
                count2--;
            }
        }
        count1 = 0;
        count2 = 0;
        for (int num : nums) {
            if (num == candidate1) {
                count1++;
            } else if (num == candidate2) {
                count2++;
            }
        }
        if (count1 > nums.length / 3) {
            res.add(candidate1);
        }
        if (count2 > nums.length / 3) {
            res.add(candidate2);
        }
        return res;
    }
}

代码解释：

1. 首先定义两个候选数 candidate1 和 candidate2，以及它们对应的计数 count1 和 count2。
2. 遍历数组，对于每个元素 num：
   • 如果 num 等于 candidate1，则 count1 加 1；
   • 如果 num 等于 candidate2，则 count2 加 1；
   • 否则，如果 count1 为 0，则将 num 设为 candidate1，并将 count1 设为 1；
   • 否则，如果 count2 为 0，则将 num 设为 candidate2，并将 count2 设为 1；
   • 否则，将 count1 和 count2 都减 1。
3. 再次遍历数组，统计 candidate1 和 candidate2 在数组中的出现次数。
4. 如果 count1 大于数组长度的三分之一，则将 candidate1 加入结果列表 res；如果 count2 大于数组长度的三分之一，则将 candidate2 加入结果列表 res。
5. 返回结果列表 res。

输出结果：

[1, 2]

总结： 本文介绍了一种使用Java代码找出数组中出现次数大于三分之一次的数的方法，该方法使用了两个候选数和计数的方式，并在最终统计候选数的出现次数来判断是否满足条件。该方法可以有效地解决该问题，代码简洁易懂。