出自剑指offer，题目如下。

我给出了两个解法以及官方解法，如下所示。

1 package com.jeaven;  2   3 /*  4 * 剑指offer_problem3: 找到数组中的重复元素  5 * */  6 public class Problem3 {  7     /*  8     * 测试  9     * */ 10     public static void main(String[] args) { 11         //测试数组 12         int[] testArray = {4,3,5,2,5,3}; 13         //解法一 14         Solution1 s1 = new Solution1(); 15         long startTime = System.nanoTime(); 16         s1.solve(testArray); 17         long endTime = System.nanoTime(); 18         long spendTime1 = endTime - startTime; 19         //解法二 20         Solution2 s2 = new Solution2(); 21         startTime = System.nanoTime(); 22         s2.solve(testArray); 23         endTime = System.nanoTime(); 24         long spendTime2 = endTime - startTime; 25         //解法三 26         int[] testArray1 = {4,3,5,2,5,3}; 27         Solution3 s3 = new Solution3(); 28         startTime = System.nanoTime(); 29         s3.solve(testArray1); 30         endTime = System.nanoTime(); 31         long spendTime3 = endTime - startTime; 32         //比较程序运行效率 33         System.out.println("solution1 spends time: " + spendTime1 + " ns"); 34         System.out.println("solution2 spends time: " + spendTime2 + " ns"); 35         System.out.println("solution3 spends time: " + spendTime3 + " ns"); 36     } 37 } 38  39  40 /* 41  * 解法一：选定某个元素，查找数组中剩下元素有没有重复的元素 42  * 时间复杂度为O(n^2) 43  * */ 44 class Solution1 { 45     public boolean solve(int[] arr) { 46         for(int i = 0; i < arr.length; i++) { 47             int curr = i; 48             for(int j = 0; j < arr.length; j++) { 49                 if(arr[j] == arr[i] && i != j) { 50                     System.out.println("solution1: " + arr[i]); 51                     return true; 52                 } 53             } 54  55         } 56         return false; 57     } 58 } 59  60  61 /* 62  * 那么优化一下 63  * 解法二：先排序，遍历数组，查看相邻元素是否重复 64  * 使用O(n)的快速排序，总的时间复杂度则为O(nlgn) 65  * */ 66 class Solution2 { 67     public boolean solve(int[] arr) { 68         //使用快速排序 69         quickSort(arr, 0, arr.length - 1); 70         int temp = 0; 71         for(int i = 1; i < arr.length; i++) { 72             if(arr[temp] == arr[i]) { 73                 System.out.println("solution2: " + arr[i]); 74                 return true; 75             } else { 76                 temp = i; 77             } 78         } 79         return false; 80     } 81  82     //快速排序partition函数 83     private int partition(int[] arr, int start, int end) { 84         //选数组第一个元素为排序基准 85         int k = start; 86         int p = start; 87         for(int q = p + 1; q <= end; q++) { 88             if(arr[q] < arr[k]) { 89                 p = p + 1; 90                 int temp = arr[p]; 91                 arr[p] = arr[q]; 92                 arr[q] = temp; 93             } 94         } 95  96         int temp = arr[p]; 97         arr[p] = arr[start]; 98         arr[start] = temp; 99         return p+1;100     }101 102     //快速排序103     private void quickSort(int[] arr, int start, int end) {104         if(start < end) {105             int k = partition(arr, start, end);106             quickSort(arr, start, k-1);107             quickSort(arr, k+1, end);108         }109     }110 111 }112 113 114 /*官方解法: 遍历数组，比较数组的下标和对应元素是否相等，如果不相等交换arr[i]和arr[arr[i]]，相等则找到重复数字*/115 class Solution3 {116     public boolean solve(int[] arr) {117         for(int i = 0; i < arr.length; i++) {118             while(arr[i] != i) {119                 if(arr[i] != arr[arr[i]]) {120                     int temp = arr[i];121                     arr[i] = arr[temp];122                     arr[temp] = temp;123                 } else {124                     System.out.println("solution3: " + arr[i]);125                     return true;126                 }127             }128         }129         return false;130     }131 }

我比较了三种方法的程序运行时间，如下图所示。显然第三种解法更好点，但是限制于题目的要求，对数组元素的范围有要求。先排序再查找的方法适合任意数组。

 

顺便一提，在写快排的时候得格外小心，我没有一次写对，还调试了一会，需要注意快排的细节，下图是快排的算法逻辑。