首页 > 代码库 > 算法--判断数组中是否有重复值

算法--判断数组中是否有重复值

 


判断数组中是否有重复值

技术分享
技术分享
技术分享
技术分享
技术分享
技术分享
 
 

第14节 重复值判断练习题

 

请设计一个高效算法,判断数组中是否有重复值。必须保证额外空间复杂度为O(1)。

给定一个int数组A及它的大小n,请返回它是否有重复值。

测试样例:
[1,2,3,4,5,5,6],7
返回:true
 
 
 
 
 
1
import java.util.*;
2

3
public class Checker {
4
    public boolean checkDuplicate(int[] a, int n) {
5
        int lastIndex = n - 1;
6
        builedMaxHeap(a,lastIndex);
7
        while(lastIndex > 0){
8
            swap(a,0,lastIndex);
9
            if(--lastIndex == 0){//如果只剩一个元素,就不用重新建堆了,排序结束
10
                break;
11
            }
12
            adjustHeap(a,0,lastIndex);
13
        }
14

15
        for(int i = 0; i < n-1; i++){
16
            if(a[i] == a[i+1])
17
                return true;
18
        }
19
        return false;
20
    }
21

22

23

24
    public void builedMaxHeap(int[] arr, int lastIndex) {
25
        //从最后一个元素的父元素开始构建最大堆
26
        int j = (lastIndex - 1)/2;
27
        while(j >= 0){
28
            int rootIndex = j;
29
            adjustHeap(arr,rootIndex,lastIndex);
30
            j--;
31
        }
32
    }
33

34
    public void adjustHeap(int[] arr, int rootIndex, int lastIndex) {
35
        int childNodeIndex = rootIndex * 2 + 1;
36

37
        while(childNodeIndex <= lastIndex){//至少有一个子节点的时候,继续循环
38
            //有右孩子,并且右孩子比左孩子大,那么childNodeIndex赋值给更大的孩子
39
            if((childNodeIndex+1) <= lastIndex && arr[childNodeIndex+1] > arr[childNodeIndex]){
40
                childNodeIndex++;
41
            }
42
            //子孩子比父亲小,说明堆构建完成,跳出循环
43
            if(arr[childNodeIndex] <= arr[rootIndex]){
44
                break;
45
            }
46
            else{
47
                swap(arr, rootIndex, childNodeIndex);
48
                rootIndex = childNodeIndex;
49
                childNodeIndex = childNodeIndex * 2 + 1;
50
            }
51
        }
52
    }
53

54
    public void swap(int[] arr, int m, int n) {
55
        int temp = arr[m];
56
        arr[m] = arr[n];
57
        arr[n] = temp;
58
    }
59
}
 
 
您的代码已保存
答案正确:恭喜!您提交的程序通过了所有的测试用例

 
 

算法--判断数组中是否有重复值