Java 数组中出现次数大于1/3的数：高效算法实现与分析

Java 代码找出数组中出现次数大于1/3的数

问题描述： 给定一个整数数组，找出数组中出现次数大于1/3的数。

算法实现：

public static void findNum(int[] nums) {
    int n = nums.length;
    int cnt1 = 0, cnt2 = 0;
    int num1 = 0, num2 = 0;
    for (int num : nums) {
        if (num == num1) {
            cnt1++;
        } else if (num == num2) {
            cnt2++;
        } else if (cnt1 == 0) {
            num1 = num;
            cnt1++;
        } else if (cnt2 == 0) {
            num2 = num;
            cnt2++;
        } else {
            cnt1--;
            cnt2--;
        }
    }
    cnt1 = 0;
    cnt2 = 0;
    for (int num : nums) {
        if (num == num1) {
            cnt1++;
        } else if (num == num2) {
            cnt2++;
        }
    }
    if (cnt1 > n / 3) {
        System.out.println(num1);
    }
    if (cnt2 > n / 3) {
        System.out.println(num2);
    }
}

算法解释：

该算法使用两个计数器cnt1和cnt2，分别记录两个候选数num1和num2出现的次数。遍历数组，对于每个元素：

1. 如果元素等于num1，则cnt1加1。
2. 如果元素等于num2，则cnt2加1。
3. 如果cnt1和cnt2都为0，则将当前元素设置为num1，并将cnt1设置为1。
4. 如果cnt1为0，则将当前元素设置为num2，并将cnt2设置为1。
5. 否则，cnt1和cnt2都减1。

最后，再次遍历数组，统计num1和num2的出现次数，如果次数大于n/3，则输出该数。

复杂度分析：

• 时间复杂度： 算法遍历数组两次，因此时间复杂度为O(n)。
• 空间复杂度： 算法只使用了常数个变量，因此空间复杂度为O(1)。

总结：

该算法高效且易于理解，可以有效地找出数组中出现次数大于1/3的数。