英文:
Remove each element that occrus more than 'N' times problem
问题
我在代码中遇到了一个小错误，希望你能帮我解决！
我有一个 ArrayList，我想要删除所有重复次数超过 'N' 次的元素。我的解决方案在大多数情况下都运行得很好，但是当 N=1 且 ArrayList 的大小大于30左右时，它会跳过一个元素，导致它不再是唯一的。它的索引是随机的（我的意思是我试图找到隐藏问题的特殊索引，但我找不到）。
以下是代码部分：
while (isSorted != true) {
for (int i = 0; i < test.size(); i++) {
counter = 0;
temp = test.get(i);
for (int j = i + 1; j < test.size(); j++) {
if (temp == test.get(j)) {
counter++;
if (counter >= maxOccurrences) {
test.remove(j);
}
}
}
if (counter < maxOccurrences) {
isSorted = true;
}
}
}
如果我再重复这个代码块一次，它会删除这个元素，一切都正常。我在试图理解为什么会跳过一个非唯一的元素。我可以在这种特殊情况下（当 N=1）使用 HashSet，但这感觉有点像作弊。
我希望我清楚地阐述了我的问题，并提供了所有所需的信息。
提前感谢你的帮助。祝一切安好！愿爱与和平与你同在！
英文:
I'm kind of stuck with a small bug in my code and I hope you could help me!
I have an ArrayList and I want to remove all the elements that repeat more than 'N' times. My solution works just fine in most cases, but when it comes to N=1 and ArrayList size is more than 30 or so it skips one element so it's not unique. Its index is random( i mean I tried to find a special index where the problem is hidden, but I could not).
Here comes the code
while(isSorted!=true) {
for (int i = 0; i < test.size(); i++) {
counter = 0;
temp = test.get(i);
for (int j = i + 1; j < test.size(); j++) {
if (temp == test.get(j)) {
counter++;
if (counter >= maxOccurrences) {
test.remove(j);
}
}
}
if(counter<maxOccurrences){
isSorted=true;
}
}
}
If I just repeat this block of code one more time it deletes this element and everything is fine. I'm trying to understand why it would skip one not unique element. I could use HashSet for this particular case(when N=1) but it feels like cheating a little bit.
I hope I was clear with my question and provided all information that is needed.
Thank you in advance. Peace and love!
答案1
得分: 2
在迭代列表时对其进行修改可能对您的健康有害。我怀疑您基于索引的循环受到对 remove 的调用所欺骗，从而导致了元素的移动。
您的算法大致为 N^3 级别。如果允许的话，考虑首先对数组进行排序，或者使用额外的存储空间，在单次遍历中通过计算数组所有元素的数量来减少搜索时间，正如另一位回答者所建议的。
英文:
Messing with a List while you're iterating over it can be hazardous to your health. I suspect that your index-based loops are getting fooled by calls to remove, which cause shifts.
Your algorithm is something on the order of N^3. Consider sorting the array first if you're allowed to do so, or using additional storage to reduce search times by counting all the array elements in a single pass as suggested by another respondent.
答案2
得分: 1
使用HashSet似乎在渐近性方面会更好，因为它不会通过总规则超过O(n)。
Map<Integer, Integer> newMap = new HashMap<>();
integers.forEach(integer -> {
if (newMap.containsKey(integer) && integer != null)
newMap.put(integer, newMap.get(integer) + 1);
else
newMap.put(integer, 1);
});
return newMap.entrySet()
.stream()
.filter(x -> x.getValue().equals(numberOfDuplicates))
.map(x -> x.getKey())
.collect(Collectors.toList())
关于你的代码，使用equals()而不是==也更好，因为如果数字大于127且小于-127，你的代码将始终不正确。
问题在于使用remove时，你需要将j减1，因为如果元素连续出现，下一个元素将移动到上一个j，你不能删除它，因为你已经在j+1元素上。
if (counter >= maxOccurrences) {
test.remove(j);
j--;
}
英文:
It seems to me that using HashSet would be better in terms of asymptotics, since it would not exceed O(n) by the sum rule.
Map<Integer, Integer> newMap = new HashMap<>();
integers.forEach(integer -> {
if(newMap.containsKey(integer) && integer != null)
newMap.put(integer, newMap.get(integer) + 1);
else
newMap.put(integer, 1);
});
return newMap.entrySet()
.stream()
.filter(x->x.getValue().equals(numberOfDuplicates))
.map(x->x.getKey())
.collect(Collectors.toList())
And what about your code it is also better to use equals() instead of ==, because if the numbers are greater than 127 and less than -127, your code will always work incorrectly.
The problem is that with remove , you need to reduce j by 1, because if the elements go in a row, the next element will move to the past j, and you won't delete it, because you're already on j+1 element
if (counter >= maxOccurrences) {
test.remove(j);
j--;
}
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库，让每个人都能够通过互相帮助和分享经验来进步。
评论