Description

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

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

测试样例:

[1,2,3,4,5,5,6],7
返回:true

Solutions

1. 排序

  采用排序方法,比较排序后的相邻两个数。这里采用堆排序:

# -*- coding:utf-8 -*-

class Checker:
    def checkDuplicate(self, a, n):
        # write code here
        if not a or n == 0:
            return False
        a = self.heapSort(a, n)
        for i in range(n-1):
            if a[i] == a[i+1]:
                return True
        return False
    
    def heapSort(self, A, n):
        # write code here
        self.build_heap(A, n)
        for i in range(n-1, -1, -1):
            A[i], A[0] = A[0], A[i]
            self.heapify(A, i, 0)
        return A
    
    def heapify(self, A, n, root_i):
        child1 = 2 * root_i + 1
        child2 = 2 * root_i + 2
        
        max_i = root_i
        
        if child1 < n and A[child1] > A[max_i]:
            max_i = child1
        if child2 < n and A[child2] > A[max_i]:
            max_i = child2
        if max_i != root_i:
            A[root_i], A[max_i] = A[max_i], A[root_i]
            self.heapify(A, n, max_i)

    def build_heap(self, A, n):
        last_node = n - 1
        parent = (last_node - 1) >> 1
        for i in range(parent, -1, -1):
            self.heapify(A, n, i)

References

  1. 重复值判断