{"id":1879,"date":"2016-03-16T22:19:26","date_gmt":"2016-03-16T14:19:26","guid":{"rendered":"http:\/\/boweihe.me\/?p=1879"},"modified":"2016-03-16T22:19:26","modified_gmt":"2016-03-16T14:19:26","slug":"leetcode-215-kth-largest-element-in-an-array","status":"publish","type":"post","link":"https:\/\/dayandcarrot.space\/?p=1879","title":{"rendered":"LeetCode 215. Kth Largest Element in an Array"},"content":{"rendered":"<p><strong>\u9898\u76ee\uff1a<\/strong>https:\/\/leetcode.com\/problems\/kth-largest-element-in-an-array\/<br \/>\n<strong>\u601d\u8def\uff1a<\/strong><br \/>\n\u627e\u7b2ck\u5927\u7684\u5143\u7d20\uff0c\u6700\u7b80\u5355\u7684\u65b9\u6cd5\u5c31\u662f\u6392\u4e2a\u5e8f\uff0c\u7136\u540e\u627e\u4e00\u4e0b\uff08\u4e2d\u4f4d\u6570\u5176\u5b9e\u4e5f\u7c7b\u4f3c\uff09\uff0c\u65f6\u95f4\u590d\u6742\u5ea6\u662fO(nlogn)<br \/>\n\u53e6\u4e00\u79cd\u65b9\u6848\u662f\uff0c\u53c2\u8003\u5feb\u901f\u6392\u5e8f\u7684\u65b9\u6cd5\u627e\u4e2apivot\uff0c\u7136\u540e\u5206\u4e09\u79cd\u60c5\u51b5\uff1a<\/p>\n<ul>\n<li>pivot\u7684\u4f4d\u7f6e\u521a\u597d\u5c31\u662f\u7b2ck\u5927\u7684\uff0c\u90a3\u4e48\u5927\u529f\u544a\u6210\uff1b<\/li>\n<li>pivot\u7684\u4f4d\u7f6e\u5728k\u524d\u5934\uff0c\u90a3\u4e48\u5c31\u5f97\u627epivot\u540e\u9762\u4e00\u5806\u4e86\uff1b<\/li>\n<li>pivot\u7684\u4f4d\u7f6e\u5728k\u540e\u5934\uff0c\u90a3\u4e48\u5f97\u627epivot\u524d\u9762\u7684\u4e00\u5806\uff1b<\/li>\n<\/ul>\n<p><strong>\u4ee3\u7801\uff1a<\/strong><\/p>\n<pre class=\"lang:c++ decode:true \">class Solution {\npublic:\n    int findKthLargest(vector&lt;int&gt;&amp; nums, int k) {\n        return findKthLargest1(nums, 0, nums.size()-1, k);\n    }\n    int findKthLargest1(vector&lt;int&gt;&amp; nums, int start, int end, int k) {\n        int small = start;\n        int large = end;\n        int pivot = nums[large];\n        while(true){\n            while(nums[small] &gt; pivot &amp;&amp; small &lt; large)\n                small ++;\n            while(nums[large] &lt;=pivot &amp;&amp; small &lt; large)\n                large --;\n            if(small == large)\n                break;\n            swap(nums, small, large);\n        }\n        swap(nums, small, end);\n        if(small == k - 1){\n            return pivot;\n        } else if (small &gt; k - 1) {\n            return findKthLargest1(nums, start, small - 1, k);\n        } else {\n            return findKthLargest1(nums, small + 1, end, k);\n        }\n    }\n    void swap(vector&lt;int&gt;&amp; nums, int small, int large) {\n        int temp = nums[small];\n        nums[small] = nums[large];\n        nums[large] = temp;\n    }\n};<\/pre>\n<p>&nbsp;<\/p>\n","protected":false},"excerpt":{"rendered":"<p>\u9898\u76ee\uff1ahttps:\/\/leetcode.com\/problems\/kth-largest-element-in-an-array\/ \u601d\u8def\uff1a \u627e\u7b2ck\u5927\u7684\u5143\u7d20\uff0c\u6700\u7b80\u5355\u7684\u65b9\u6cd5\u5c31\u662f\u6392\u4e2a\u5e8f\uff0c\u7136\u540e\u627e\u4e00\u4e0b\uff08\u4e2d\u4f4d\u6570\u5176\u5b9e\u4e5f\u7c7b\u4f3c\uff09\uff0c\u65f6\u95f4\u590d\u6742\u5ea6\u662fO(nlogn) \u53e6\u4e00\u79cd\u65b9\u6848\u662f\uff0c\u53c2\u8003\u5feb\u901f\u6392\u5e8f\u7684\u65b9\u6cd5\u627e\u4e2apivot\uff0c\u7136\u540e\u5206\u4e09\u79cd\u60c5\u51b5\uff1a pivot\u7684\u4f4d\u7f6e\u521a\u597d\u5c31\u662f\u7b2ck\u5927\u7684\uff0c\u90a3\u4e48\u5927\u529f\u544a\u6210\uff1b pivot\u7684\u4f4d\u7f6e\u5728k\u524d\u5934\uff0c\u90a3\u4e48\u5c31\u5f97\u627epivot\u540e\u9762\u4e00\u5806\u4e86\uff1b pivot\u7684\u4f4d\u7f6e\u5728k\u540e\u5934\uff0c\u90a3\u4e48\u5f97\u627epivot\u524d\u9762\u7684\u4e00\u5806\uff1b \u4ee3\u7801\uff1a class Solution { public: int findKthLargest(vector&lt;int&gt;&amp; nums, int k) { return findKthLargest1(nums, 0, nums.size()-1, k); } int findKthLargest1(vector&lt;int&gt;&amp; nums, int start, int end, int k) { int small = start; int large = end; int pivot = nums[large]; while(true){ while(nums[small] &gt; pivot &amp;&amp; small &lt; large) small [&hellip;]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[4],"tags":[66],"class_list":["post-1879","post","type-post","status-publish","format-standard","hentry","category-study","tag-leetcode-oj"],"_links":{"self":[{"href":"https:\/\/dayandcarrot.space\/index.php?rest_route=\/wp\/v2\/posts\/1879","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/dayandcarrot.space\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/dayandcarrot.space\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/dayandcarrot.space\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/dayandcarrot.space\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=1879"}],"version-history":[{"count":0,"href":"https:\/\/dayandcarrot.space\/index.php?rest_route=\/wp\/v2\/posts\/1879\/revisions"}],"wp:attachment":[{"href":"https:\/\/dayandcarrot.space\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=1879"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/dayandcarrot.space\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=1879"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/dayandcarrot.space\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=1879"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}