笔试——查找重复数（杭州某准独角兽）

妖狐艹你老母 2022-10-05 06:51 88阅读 0赞

# 题目描述 #

> 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 一组数字的查重算法][java]

[java]: https://blog.csdn.net/sinat_34322082/article/details/53121660