当前位置 博文首页 > 无限迭代中......:笔试——查找重复数(杭州某准独角兽)
java编码实现在整数数组中找到重复的数字,要求复杂度低于O(N*N)
/**
* 使用Arrays类中的sort方法实现排序,然后用后面的值与前面的一个比较,重复则加入到新数组之中
* @param arr 待去重数组
* @return 升序的去重的数组
*/
public static int[] sortToReduce(int[] arr){
Arrays.sort(arr);
int index=0;
int count = 0;
for (int i = 1; i < arr.length; i++) {
if (arr[i]!=arr[index]) {
if(index + 1 != i){
arr[count++]=arr[index];
}
index = i;
}
}
int[] desArray=new int[count];
if (desArray.length > 0) System.arraycopy(arr, 0, desArray, 0, desArray.length);
return desArray;
}
/**
* @author ShenTuZhiGang
* @version 1.0.0
* @email 1600337300@qq.com
* @date 2021-06-07 18:41
*/
public class ArrayTest {
@Test
public void test(){
assertArrayEquals(new int[]{},sortToReduce(new int[]{}));
assertArrayEquals(new int[]{1,3,4},sortToReduce(new int[]{0, 1, 1, 2, 3, 4, 1, 3, 4, 5}));
assertArrayEquals(new int[]{3,4},sortToReduce(new int[]{0, 1, 2, 3, 4, 3, 4, 5}));
}
/**
* 使用Arrays类中的sort方法实现排序,然后用后面的值与前面的一个比较,重复则加入到新数组之中
* @param arr 待去重数组
* @return 升序的去重的数组
*/
public static int[] sortToReduce(int[] arr){
Arrays.sort(arr);
int index=0;
int count = 0;
for (int i = 1; i < arr.length; i++) {
if (arr[i]!=arr[index]) {
if(index + 1 != i){
arr[count++]=arr[index];
}
index = i;
}
}
int[] desArray=new int[count];
if (desArray.length > 0) System.arraycopy(arr, 0, desArray, 0, desArray.length);
return desArray;
}
}
java 一组数字的查重算法
cs