Duplicates in a sorted java array(已排序的 java 数组中的重复项)
问题描述
我必须编写一个方法,该方法接受一个已经按数字顺序排序的整数数组,然后删除所有重复的数字并返回一个仅包含没有重复的数字的数组.然后必须打印出该数组,因此我不能有任何空指针异常.该方法必须在 O(n) 时间内,不能使用向量或散列.这是我到目前为止所拥有的,但它只有前几个数字按顺序排列,没有重复,然后将重复的数字放在数组的后面.我无法创建临时数组,因为它给了我空指针异常.
I have to write a method that takes an array of ints that is already sorted in numerical order then remove all the duplicate numbers and return an array of just the numbers that have no duplicates. That array must then be printed out so I can't have any null pointer exceptions. The method has to be in O(n) time, can't use vectors or hashes. This is what I have so far but it only has the first couple numbers in order without duplicates and then just puts the duplicates in the back of the array. I can't create a temporary array because it gives me null pointer exceptions.
public static int[] noDups(int[] myArray) {
int j = 0;
for (int i = 1; i < myArray.length; i++) {
if (myArray[i] != myArray[j]) {
j++;
myArray[j] = myArray[i];
}
}
return myArray;
}
推荐答案
由于这似乎是作业,我不想给你确切的代码,但这里是做什么:
Since this seems to be homework I don't want to give you the exact code, but here's what to do:
- 对数组进行第一次遍历,看看有多少重复项
- 创建一个新的大小数组(oldSize - 重复)
- 再次遍历数组以将唯一值放入新数组中
由于数组已排序,您只需检查 array[n] == array[n+1].如果不是,那么它不是重复的.检查 n+1 时请注意数组边界.
Since the array is sorted, you can just check if array[n] == array[n+1]. If not, then it isn't a duplicate. Be careful about your array bounds when checking n+1.
因为这涉及到两次运行,它将在 O(2n) -> O(n) 时间内运行.
edit: because this involves two run throughs it will run in O(2n) -> O(n) time.
这篇关于已排序的 java 数组中的重复项的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持编程学习网!
本文标题为:已排序的 java 数组中的重复项
基础教程推荐
- 如何对 HashSet 进行排序? 2022-01-01
- 如何使用 Eclipse 检查调试符号状态? 2022-01-01
- Java 中保存最后 N 个元素的大小受限队列 2022-01-01
- 首次使用 Hadoop,MapReduce Job 不运行 Reduce Phase 2022-01-01
- 如何使用 Stream 在集合中拆分奇数和偶数以及两者的总和 2022-01-01
- 由于对所需库 rt.jar 的限制,对类的访问限制? 2022-01-01
- 如何强制对超级方法进行多态调用? 2022-01-01
- 在螺旋中写一个字符串 2022-01-01
- Spring Boot Freemarker从2.2.0升级失败 2022-01-01
- 如何在不安装整个 WTP 包的情况下将 Tomcat 8 添加到 Eclipse Kepler 2022-01-01