{"id":5625,"date":"2021-11-11T23:57:19","date_gmt":"2021-11-11T15:57:19","guid":{"rendered":"https:\/\/damogame.cn:15443\/wordpress\/?p=5625"},"modified":"2021-11-12T23:19:14","modified_gmt":"2021-11-12T15:19:14","slug":"%e7%8e%8b%e4%ba%89%e7%9a%84%e5%bf%ab%e6%8e%92%e5%88%86%e5%8c%ba%e6%96%b9%e6%b3%95%e7%9c%9f%e7%ae%80%e6%b4%81","status":"publish","type":"post","link":"https:\/\/i007.cc\/wordpress\/archives\/5625","title":{"rendered":"\u738b\u4e89\u7684\u5feb\u6392\u5206\u533a\u65b9\u6cd5\u771f\u7b80\u6d01"},"content":{"rendered":"<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"cpp\">int Patition(vector&lt;int&gt;&amp; v, int begin, int end) {\r\n    int&amp; pivot = v[end];\r\n    int done = begin;\r\n    for (int i = begin; i &lt; end; ++i) {\r\n        if (v[i] &lt; pivot) {\r\n            std::swap(v[i], v[done]);\r\n            done++;\r\n        }\r\n    }\r\n    std::swap(v[done], pivot);\r\n    return done;\r\n}<\/pre>\n<p>&nbsp;<\/p>\n<p>\u83b7\u5f97\u7b2c\u51e0\u5927\u5143\u7d20<\/p>\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"generic\">class Solution {\r\npublic:\r\n    int findKthLargest(vector&lt;int&gt;&amp; nums, int k) {\r\n        if (k &lt;= 0 || k &gt; nums.size()) {\r\n            throw \"wrong input\";\r\n        }\r\n\r\n        return findKthLargest(nums, 0, nums.size() - 1, k);\r\n    }\r\n\r\n    int findKthLargest(vector&lt;int&gt;&amp; nums, int begin, int end, int k) {\r\n        if (begin &gt;= end)\r\n            return nums[begin];\r\n\r\n        int pivot = patition(nums, begin, end);\r\n        if (pivot == k - 1) {\r\n            return nums[pivot];\r\n        } else if (pivot &gt; k - 1) {\r\n            return findKthLargest(nums, begin, pivot - 1, k);\r\n        } else {\r\n            return findKthLargest(nums, pivot + 1, end, k);\r\n        }\r\n    }\r\n\r\n    int patition(vector&lt;int&gt;&amp; nums, int begin, int end) {\r\n        int rand_pos = begin + rand() % (end - begin + 1);\r\n        if (rand_pos != end)\r\n            std::swap(nums[end], nums[rand_pos]);\r\n\r\n        int&amp; pivot = nums[end];\r\n        int done = begin;\r\n        for (int i = begin; i &lt; end; ++i) {\r\n            if (nums[i] &gt; pivot) {\r\n                std::swap(nums[i], nums[done]);\r\n                done++;\r\n            }\r\n        }\r\n\r\n        std::swap(nums[done], pivot);\r\n        return done;\r\n    }\r\n};<\/pre>\n<p>&nbsp;<\/p>\n","protected":false},"excerpt":{"rendered":"<p>int Patition(vector&#038;<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"colormag_page_container_layout":"default_layout","colormag_page_sidebar_layout":"default_layout","footnotes":""},"categories":[],"tags":[120],"class_list":["post-5625","post","type-post","status-publish","format-standard","hentry","tag-04-"],"_links":{"self":[{"href":"https:\/\/i007.cc\/wordpress\/wp-json\/wp\/v2\/posts\/5625","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/i007.cc\/wordpress\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/i007.cc\/wordpress\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/i007.cc\/wordpress\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/i007.cc\/wordpress\/wp-json\/wp\/v2\/comments?post=5625"}],"version-history":[{"count":0,"href":"https:\/\/i007.cc\/wordpress\/wp-json\/wp\/v2\/posts\/5625\/revisions"}],"wp:attachment":[{"href":"https:\/\/i007.cc\/wordpress\/wp-json\/wp\/v2\/media?parent=5625"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/i007.cc\/wordpress\/wp-json\/wp\/v2\/categories?post=5625"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/i007.cc\/wordpress\/wp-json\/wp\/v2\/tags?post=5625"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}