217. Contains Duplicate

一、题目

　　1、审题

　　2、分析

　　　　判断一个数组中是否有重复的元素

二、解答

　　1、思路：

　　　　方法一、

　　　　　　先排序，在判断

1     public boolean containsDuplicate(int[] nums) {
2         
3         Arrays.sort(nums);
4         for (int i = 1; i < nums.length; i++) {
5             if(nums[i] == nums[i - 1])
6                 return true;
7         }
8         return false;
9     }

　　　　方法二、

　　　　　　使用优先队列 PriorityQueue 对数组进行排序

 1     public boolean containsDuplicate2(int[] nums) {
 2         
 3         PriorityQueue<Integer> queue = new PriorityQueue<>();
 4         for(int i: nums)
 5             queue.offer(i);
 6         int tmp = -1;
 7         while(!queue.isEmpty()) {
 8             int cur = queue.poll();
 9             if(cur == tmp)
10                 return true;
11             tmp = cur;
12         }
13         return false;
14     }

　　　　方法三、

　　　　　　使用选择排序对数组进行排序，在判断。

　　　　　　注意：为了提高选择排序的效率（即避免基本有序时的最坏情况），可以先对数组元素进行乱序。

 1     public boolean containsDuplicate3(int[] nums) {
 2         
 3         shuffle(nums);
 4         int low = 0, high = nums.length - 1;
 5         selectionSort(nums, low, high);
 6         for (int i = 1; i < nums.length; i++) {
 7             if(nums[i] == nums[i - 1])
 8                 return true;
 9         }
10         return false;
11     }
12     
13     private void shuffle(int[] nums) {
14         Random random = new Random();
15         for (int i = 1; i < nums.length; i++) {
16             int r = random.nextInt(i + 1);
17             exchange(nums, i, r);
18         }
19     }
20 
21     private void selectionSort(int[] nums, int low, int high) {
22         
23         if(low >= high)
24             return;
25         int i = low, j = high + 1;
26         while(i < j) {
27             while((i + 1 <= high) && nums[++i] < nums[low]);    // 从左向右找比 low 大的
28             while((j - 1 >= low) && nums[low] < nums[--j]);    // 从右向左找比 low 小的
29             if(i < j)
30                 exchange(nums, i, j);
31             else
32                 break;
33         }
34         exchange(nums, low, j);
35         selectionSort(nums, low, j - 1);
36         selectionSort(nums, j + 1, high);
37     }
38     private void exchange(int[] nums, int i, int j) {
39         int tmp = nums[i];
40         nums[i] = nums[j];
41         nums[j] = tmp;
42     }