Find the Duplicate Number leetcode 287 - 5ibc.net
题目大意：找到数组中唯一的一个重复的数值。时间复杂度要小于O(n^2)，不能修改数组了。
发现一个很6的算法，把数组当成一个静态链表，也就是说nums[]，数组相当于next[]，0为起始节点，节点地址范围就是0-n，一共n+1个节点。
因为数组范围是1-n，所以没有节点next会指向0。
而在有n+1个，next指针的情况下，链表必然会出现环，也就是两个next指向同一个节点，所以这题其实是相当于寻找链表的环的起始点（方法就是快慢指针，快指针在环里追上慢指针，再让一个指针跑到起始点，然后两个指针同速而行，交点就是答案）。
Read full article from Find the Duplicate Number leetcode 287 - 5ibc.net
No comments:
Post a Comment