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


No comments:

Post a Comment

Labels

Algorithm (219) Lucene (130) LeetCode (97) Database (36) Data Structure (33) text mining (28) Solr (27) java (27) Mathematical Algorithm (26) Difficult Algorithm (25) Logic Thinking (23) Puzzles (23) Bit Algorithms (22) Math (21) List (20) Dynamic Programming (19) Linux (19) Tree (18) Machine Learning (15) EPI (11) Queue (11) Smart Algorithm (11) Operating System (9) Java Basic (8) Recursive Algorithm (8) Stack (8) Eclipse (7) Scala (7) Tika (7) J2EE (6) Monitoring (6) Trie (6) Concurrency (5) Geometry Algorithm (5) Greedy Algorithm (5) Mahout (5) MySQL (5) xpost (5) C (4) Interview (4) Vi (4) regular expression (4) to-do (4) C++ (3) Chrome (3) Divide and Conquer (3) Graph Algorithm (3) Permutation (3) Powershell (3) Random (3) Segment Tree (3) UIMA (3) Union-Find (3) Video (3) Virtualization (3) Windows (3) XML (3) Advanced Data Structure (2) Android (2) Bash (2) Classic Algorithm (2) Debugging (2) Design Pattern (2) Google (2) Hadoop (2) Java Collections (2) Markov Chains (2) Probabilities (2) Shell (2) Site (2) Web Development (2) Workplace (2) angularjs (2) .Net (1) Amazon Interview (1) Android Studio (1) Array (1) Boilerpipe (1) Book Notes (1) ChromeOS (1) Chromebook (1) Codility (1) Desgin (1) Design (1) Divide and Conqure (1) GAE (1) Google Interview (1) Great Stuff (1) Hash (1) High Tech Companies (1) Improving (1) LifeTips (1) Maven (1) Network (1) Performance (1) Programming (1) Resources (1) Sampling (1) Sed (1) Smart Thinking (1) Sort (1) Spark (1) Stanford NLP (1) System Design (1) Trove (1) VIP (1) tools (1)

Popular Posts