笔试题：在整数数组中找到重复的数字

- 日理万妓 2023-02-20 03:25 47阅读 0赞

**题目描述：**  
java编码实现在整数数组中找到重复的数字，要求复杂度低于O(N\*N)  
**解题思路：**  
我用两种方法进行解答，其一是用桶的思想，其二是排序  
**程序代码：**

public class Main {
    
        public static void main(String[] args) {
            int[] a = {1,1,6,5,5,5,-10,-10};
    //    int[] a = {1,1,1,6,5,5,10,10};
    //    int[] a = {-5,-5,-8,-8};
    //    int[] a = {5};
    
            int[] b = new int[110];
            int maxn = -(1<<31);
            int minn = (1<<31) - 1;
    
            System.out.print("原数据：");
            for (int i : a) {
                System.out.print(i + " ");
            }
            System.out.println("\n第一种时间复杂度大约是O(n)或O(数组中最大值减最小值)");
            // 找出数组中最大值和最小值
            for (int i = 0; i < a.length; i ++) {
                if (a[i] > maxn) {
                    maxn = a[i];
                }
                if (a[i] < minn) {
                    minn = a[i];
                }
            }
    
            // 将a数组的值，以索引的思想存到b数组中
            for (int i = 0; i < a.length; i ++) {
                b[a[i] - minn] ++;
            }
    
            // 遍历b数组中的索引，找出出现次数大于1的
            for (int i = 0; i <= maxn - minn; i ++) {
                if (b[i] > 1) {
                    System.out.print(i + minn + " ");
                }
            }
    
    
            System.out.println("\n第二种是先快排，然后找出出现多次的元素，再进行去重");
            // 如果数据差较大，先进行排序
            int len = a.length;
            int j = 0;
            if (len > 1) {
                quickSort(a,0,len - 1);
                for (int i = 1; i < len; i++) {
                    if (a[i] == a[i-1]) {
                        b[j ++] = a[i];
                    }
                }
            }
    
            // 去重
            if (j > 0) {
                System.out.print(b[0]);
                for (int i = 1; i < j; i++) {
                    if (b[i] != b[i - 1]) {
                        System.out.print(" " + b[i]);
                    }
                }
            }
    
        }
        static void quickSort(int a[],int left,int right) {
            int i, j, temp;
            i = left;
            j = right;
            if (i >= j) {
                return;
            }
            while (i < j) {
                while (i < j && a[j] >= a[left]) {
                    j --;
                }
                while (i < j && a[i] <= a[left]) {
                    i ++;
                }
                temp = a[i];
                a[i] = a[j];
                a[j] = temp;
    
            }
            temp = a[i];
            a[i] = a[left];
            a[left] = temp;
            quickSort(a,left,i - 1);
            quickSort(a,i + 1,right);
        }
    }

**运行结果：**  
![在这里插入图片描述][20200623092408819.png]

[20200623092408819.png]: https://img-blog.csdnimg.cn/20200623092408819.png