以下数组中多数元素的代码适用于 n/2
元素的时间,但不适用于 n/3
时代。有人能帮我吗?
class Solution {
public List<Integer> majorityElement(int[] a) {
ArrayList<Integer> arr = new ArrayList<>();
int flag=0;
for (int i = 0; i < a.length; i++) {
int count = 0;
for (int j = i; j < a.length; j++) {
if (a[i] == a[j])
count++;
}
if (count > a.length/3) {
arr.add(a[i]);
flag=1;
}
}
if (flag==0)
return new ArrayList<>();
return arr;
}
}
2条答案
按热度按时间332nm8kg1#
为了计算每个元素的频率,您需要从i=0到n和j=0到n进行遍历,如果您使用hashmap来解决它会更好,现在的时间复杂度是o(n2),使用hashmap您可以在o(n)中解决它
https://www.geeksforgeeks.org/majority-element/
hujrc8aj2#
您缺少索引低于的所有元素
i
在第二个for循环中。要计算一个数字的频率,您需要将它与数组中存在的所有元素相等,如果从count = 0
.以下是修改后的版本: