{"id":3554,"date":"2020-08-13T20:17:35","date_gmt":"2020-08-13T12:17:35","guid":{"rendered":"http:\/\/www.sniper97.cn\/?p=3554"},"modified":"2020-08-13T20:17:35","modified_gmt":"2020-08-13T12:17:35","slug":"%e3%80%90leetcode%e3%80%91l0287-%e5%af%bb%e6%89%be%e9%87%8d%e5%a4%8d%e6%95%b0","status":"publish","type":"post","link":"http:\/\/www.sniper97.cn\/index.php\/note\/algorithm\/3554\/","title":{"rendered":"\u3010LeetCode\u3011*0287 \u5bfb\u627e\u91cd\u590d\u6570"},"content":{"rendered":"\n

https:\/\/leetcode-cn.com\/problems\/find-the-duplicate-number\/<\/a><\/p>\n\n\n

\u597d\u4e45\u4e0d\u5199LeetCode\u7684\u4e86\uff0c\u4e3b\u8981\u662f\u6700\u8fd1\u6709\u70b9\u643a\u5e26\u5237\u9898\u4e86\uff0c\u518d\u52a0\u4e0a\u597d\u591a\u9898\uff0c\u4e5f\u6ca1\u4ec0\u4e48\u8425\u517b\u3002<\/p>\n\n\n

\u4e3a\u4e86\u627e\u56de\u4e00\u4e0b\u72b6\u6001\uff0c\u627e\u4e00\u4e9b\u5178\u578b\u9898\u91cd\u65b0\u5f00\u59cb\u5199\u3002<\/p>\n\n\n

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

\"\"\"
<\/em>      \u250f\u251b \u253b\u2501\u2501\u2501\u2501\u2501\u251b \u253b\u2513
<\/em>      \u2503<\/em>\u3000\u3000\u3000\u3000\u3000\u3000<\/em> \u2503
<\/em>      \u2503<\/em>\u3000\u3000\u3000<\/em>\u2501<\/em>\u3000\u3000\u3000<\/em>\u2503
<\/em>      \u2503<\/em>\u3000<\/em>\u2533\u251b<\/em>\u3000<\/em>  \u2517\u2533<\/em>\u3000<\/em>\u2503
<\/em>      \u2503<\/em>\u3000\u3000\u3000\u3000\u3000\u3000<\/em> \u2503
<\/em>      \u2503<\/em>\u3000\u3000\u3000<\/em>\u253b<\/em>\u3000\u3000\u3000<\/em>\u2503
<\/em>      \u2503<\/em>\u3000\u3000\u3000\u3000\u3000\u3000<\/em> \u2503
<\/em>      \u2517\u2501\u2513<\/em>\u3000\u3000\u3000<\/em>\u250f\u2501\u2501\u2501\u251b
<\/em>        \u2503<\/em>\u3000\u3000\u3000<\/em>\u2503   <\/em>\u795e\u517d\u4fdd\u4f51<\/em>
<\/em>        \u2503<\/em>\u3000\u3000\u3000<\/em>\u2503   <\/em>\u4ee3\u7801\u65e0<\/em>BUG<\/em>\uff01<\/em>
<\/em>        \u2503<\/em>\u3000\u3000\u3000<\/em>\u2517\u2501\u2501\u2501\u2501\u2501\u2501\u2501\u2501\u2501\u2513
<\/em>        \u2503<\/em>\u3000\u3000\u3000\u3000\u3000\u3000\u3000<\/em>    \u2523\u2513
<\/em>        \u2503<\/em>\u3000\u3000\u3000\u3000<\/em>         \u250f\u251b
<\/em>        \u2517\u2501\u2513 \u2513 \u250f\u2501\u2501\u2501\u2533 \u2513 \u250f\u2501\u251b
<\/em>          \u2503 \u252b \u252b   \u2503 \u252b \u252b
<\/em>          \u2517\u2501\u253b\u2501\u251b   \u2517\u2501\u253b\u2501\u251b
<\/em>\"\"\"
<\/em>
<\/em>
<\/em>class Solution(object):
    def findDuplicate(self, nums):
        \"\"\"
<\/em>        <\/em>:type<\/em><\/strong> nums: List[int]
<\/em>        <\/em>:rtype<\/em><\/strong>: int
<\/em>        \"\"\"
<\/em>        <\/em>res = 0
        fast = 0
        while res != fast or fast == 0:
            res = nums[res]
            fast = nums[nums[fast]]
            print()
        print(res)
        i = 0
        while res != i:
            res = nums[res]
            i = nums[i]
        return res


if __name__ == '__main__':
    nums = [1, 2, 3, 4, 2, 2]
    nums = [2, 5, 9, 6, 9, 3, 8, 9, 7, 1]
    print(Solution().findDuplicate(nums))
<\/pre>\n\n\n
\u601d\u8def\uff1a<\/p>\n\n\n
\u8fd9\u9053\u9898\u9996\u5148\u5c31\u662f\u4e00\u4e2a\u5feb\u6162\u6307\u9488\u95ee\u9898\u2014\u2014 \u5feb\u6162\u6307\u9488\u662f\u4e00\u4e2a\u53ef\u4ee5\u7528\u4e8e\u5f88\u591a\u95ee\u9898\u7684\u6280\u5de7\u3002 <\/p>\n\n\n
\u5feb\u6162\u6307\u9488\u4e2d\u7684\u5feb\u6162\u6307\u7684\u662f\u6307\u9488\u5411\u524d\u79fb\u52a8\u7684\u6b65\u957f\uff0c\u6bcf\u6b21\u79fb\u52a8\u7684\u6b65\u957f\u8f83\u5927\u5373\u4e3a\u5feb\uff0c\u6b65\u957f\u8f83\u5c0f\u5373\u4e3a\u6162\uff0c\u5e38\u7528\u7684\u5feb\u6162\u6307\u9488\u4e00\u822c\u662f\u5728\u5355\u94fe\u8868\u4e2d\u8ba9\u5feb\u6307\u9488\u6bcf\u6b21\u5411\u524d\u79fb\u52a82\uff0c\u6162\u6307\u9488\u5219\u6bcf\u6b21\u5411\u524d\u79fb\u52a81\u3002\u5feb\u6162\u4e24\u4e2a\u6307\u9488\u90fd\u4ece\u94fe\u8868\u5934\u5f00\u59cb\u904d\u5386\uff0c\u4e8e\u662f\u5feb\u6307\u9488\u5230\u8fbe\u94fe\u8868\u672b\u5c3e\u7684\u65f6\u5019\u6162\u6307\u9488\u521a\u597d\u5230\u8fbe\u4e2d\u95f4\u4f4d\u7f6e\uff0c\u4e8e\u662f\u53ef\u4ee5\u5f97\u5230\u4e2d\u95f4\u5143\u7d20\u7684\u503c\u3002\u5feb\u6162\u6307\u9488\u5728\u94fe\u8868\u76f8\u5173\u95ee\u9898\u4e2d\u4e3b\u8981\u6709\u4e24\u4e2a\u5e94\u7528\uff1a<\/p>\n\n\n
  •  \u5feb\u901f\u627e\u51fa\u672a\u77e5\u957f\u5ea6\u5355\u94fe\u8868\u7684\u4e2d\u95f4\u8282\u70b9 \u8bbe\u7f6e\u4e24\u4e2a\u6307\u9488 *fast\u3001*slow \u90fd\u6307\u5411\u5355\u94fe\u8868\u7684\u5934\u8282\u70b9\uff0c\u5176\u4e2d*fast\u7684\u79fb\u52a8\u901f\u5ea6\u662f*slow\u76842\u500d\uff0c\u5f53*fast\u6307\u5411\u672b\u5c3e\u8282\u70b9\u7684\u65f6\u5019\uff0cslow\u6b63\u597d\u5c31\u5728\u4e2d\u95f4\u4e86\u3002 <\/li>
  •  \u5224\u65ad\u5355\u94fe\u8868\u662f\u5426\u6709\u73af \u5229\u7528\u5feb\u6162\u6307\u9488\u7684\u539f\u7406\uff0c\u540c\u6837\u8bbe\u7f6e\u4e24\u4e2a\u6307\u9488 *fast\u3001*slow \u90fd\u6307\u5411\u5355\u94fe\u8868\u7684\u5934\u8282\u70b9\uff0c\u5176\u4e2d  *fast\u7684\u79fb\u52a8\u901f\u5ea6\u662f*slow\u76842\u500d\u3002\u5982\u679c *fast = NULL\uff0c\u8bf4\u660e\u8be5\u5355\u94fe\u8868 \u4ee5 NULL\u7ed3\u5c3e\uff0c\u4e0d\u662f\u5faa\u73af\u94fe\u8868\uff1b\u5982\u679c *fast =  *slow\uff0c\u5219\u5feb\u6307\u9488\u8ffd\u4e0a\u6162\u6307\u9488\uff0c\u8bf4\u660e\u8be5\u94fe\u8868\u662f\u5faa\u73af\u94fe\u8868\u3002 <\/li><\/ul>\n\n\n
    \u6bd4\u5982\u6211\u4eec\u4e3e\u4e2a\u4f8b\u5b50\uff1a<\/p>\n\n\n
    \u6709 \u5217\u8868 \u30102\uff0c5\uff0c9\uff0c6\uff0c9\uff0c3\uff0c8\uff0c9\uff0c7\uff0c1\u3011<\/p>\n\n\n
    \u6211\u4eec\u53ef\u4ee5\u6839\u636e\u7d22\u5f15\uff0c\u5c06\u5217\u8868\u8f6c\u6362\u4e3a\u94fe\u8868\uff1a<\/p>\n\n\n
    2->9->1->5->3->6->8->7->9<\/p>\n\n\n
    \u4e3a\u4e86\u9632\u6b62\u753b\u4e71\uff0c\u53ea\u753b\u51fa\u51e0\u6b65\uff1a<\/p>\n\n\n
    \"\"<\/figure><\/div>\n\n\n
    \u8fd9\u6837\uff0c\u6211\u4eec\u5c31\u53ef\u4ee5\u5f97\u5230\u4e00\u4e2a\u7c7b\u4f3c\u7684\u94fe\u8868\uff1a<\/p>\n\n\n
    \"\"<\/figure><\/div>\n\n\n
    \u6211\u4eec\u4f7f\u7528\u5feb\u6162\u6307\u9488\u540e\uff0c\u5feb\u6162\u6307\u9488\u4f1a\u5728\u6570\u5b578\u5904\u76f8\u9047\u3002<\/p>\n\n\n
    \u5230\u8fd9\u91cc\uff0c\u6211\u4eec\u5c31\u53ef\u4ee5\u77e5\u9053\uff0c\u6162\u6307\u9488\u4ece\u6570\u5b572\u5230\u6570\u5b578\uff0c\u5feb\u6307\u9488\u4ece\u6570\u5b572\u7ed5\u4e00\u5708\u540e\u5230\u6570\u5b578\uff0c\u4e5f\u5c31\u662f\u5feb\u7684\u6bd4\u6162\u7684\u591a\u8d70\u4e86\u4e00\u5708\u3002<\/p>\n\n\n
    \u90a3\u5982\u679c\uff0c\u6211\u4eec\u5c06\u6162\u7684\u653e\u56de\u8d77\u70b9\uff0c\u4ed6\u4eec\u5c31\u4f1a\u5728\u5708\u7684\u8d77\u59cb\u5730\u76f8\u9047\uff0c\u5c31\u662f\u6570\u5b579\u3002<\/p>\n\n\n
    \u5c31\u7c7b\u4f3c\u4e8e\uff0c\u6211\u8dd1100\u7c73\u80fd\u843d\u4f6020\u7c73\uff0c\u90a3\u5982\u679c\u4f60\u6bd4\u6211\u63d0\u524d20\u7c73\u8dd1\uff0c\u90a3\u4e48\u6211\u4eec\u5c31\u4f1a\u540c\u65f6\u5230\u7ec8\u70b9\u3002<\/p>\n","protected":false},"excerpt":{"rendered":"
    https:\/\/leetcode-cn.com\/problems\/find-the-duplicat […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"om_disable_all_campaigns":false,"_mi_skip_tracking":false,"_monsterinsights_sitenote_active":false,"_monsterinsights_sitenote_note":"","_monsterinsights_sitenote_category":0,"footnotes":""},"categories":[10],"tags":[],"views":2673,"_links":{"self":[{"href":"http:\/\/www.sniper97.cn\/index.php\/wp-json\/wp\/v2\/posts\/3554"}],"collection":[{"href":"http:\/\/www.sniper97.cn\/index.php\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"http:\/\/www.sniper97.cn\/index.php\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"http:\/\/www.sniper97.cn\/index.php\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"http:\/\/www.sniper97.cn\/index.php\/wp-json\/wp\/v2\/comments?post=3554"}],"version-history":[{"count":0,"href":"http:\/\/www.sniper97.cn\/index.php\/wp-json\/wp\/v2\/posts\/3554\/revisions"}],"wp:attachment":[{"href":"http:\/\/www.sniper97.cn\/index.php\/wp-json\/wp\/v2\/media?parent=3554"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/www.sniper97.cn\/index.php\/wp-json\/wp\/v2\/categories?post=3554"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/www.sniper97.cn\/index.php\/wp-json\/wp\/v2\/tags?post=3554"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}