The Duplicate Detection Problem | Algorithms Notes

The Duplicate Detection Problem | Algorithms Notes

Given an integer array A of length n, such that each integer is in the range [1, n-1]. Array A is read-only. Design an linear time algorithm to find one duplicate element using O(1) variables.

Solution:

Since each element has a value in [1, n-1], we can consider each element as a node in the linked list, that is, element i points to element A[i]. Since no node can point to node n, we can consider node n as the head of this linked list. If node i is pointed by more than one element, then i is a duplicate value in the array. Thus, we can use classical cycle detection algorithm to find the head of the cycle, which is a duplicate element.

解法：

因為每個元素的值都在[1, n-1]之中，我們可以把每個元素當作是一個串列的結點，意即元素i指向元素A[i]。 因為沒有一個元素可以指向結點n，我們可以把節點n視為串列的頭部。此外，如果節點i被超過一個以上的結點所指向的話，那就代表i在陣列中是重複的元素。因此，我們可以使用迴圈偵測演算法來找出迴圈的頭部，此元素必為陣列中的重複元素。

Read full article from The Duplicate Detection Problem | Algorithms Notes