123132129122请用Java代码找出这个数组中出现次数大于13的数输出
以下是Java代码实现:
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);
}
}
这个算法的时间复杂度为O(n),空间复杂度为O(1)。
原文地址: https://www.cveoy.top/t/topic/E1R 著作权归作者所有。请勿转载和采集!