{"id":237,"date":"2024-01-12T00:47:25","date_gmt":"2024-01-11T16:47:25","guid":{"rendered":"https:\/\/wangqianming.top\/?p=237"},"modified":"2024-01-12T00:47:25","modified_gmt":"2024-01-11T16:47:25","slug":"%e6%9c%80%e5%a4%a7%e5%a0%86%e4%b8%8e%e5%bf%ab%e6%8e%92%e7%9a%84%e4%be%8b%e5%ad%90","status":"publish","type":"post","link":"https:\/\/wangqianming.top\/index.php\/2024\/01\/12\/%e6%9c%80%e5%a4%a7%e5%a0%86%e4%b8%8e%e5%bf%ab%e6%8e%92%e7%9a%84%e4%be%8b%e5%ad%90\/","title":{"rendered":"\u6700\u5927\u5806\u4e0e\u5feb\u6392\u7684\u4f8b\u5b50"},"content":{"rendered":"

\u6570\u7ec4\u4e2d\u7b2ck\u4e2a\u6700\u5927\u5143\u7d20<\/h1>\n

\u7ed9\u5b9a\u6574\u6570\u6570\u7ec4 nums<\/code> \u548c\u6574\u6570 k<\/code>\uff0c\u8bf7\u8fd4\u56de\u6570\u7ec4\u4e2d\u7b2c k<\/code> \u4e2a\u6700\u5927\u7684\u5143\u7d20\u3002<\/p>\n

\u8bf7\u6ce8\u610f\uff0c\u4f60\u9700\u8981\u627e\u7684\u662f\u6570\u7ec4\u6392\u5e8f\u540e\u7684\u7b2c k<\/code> \u4e2a\u6700\u5927\u7684\u5143\u7d20\uff0c\u800c\u4e0d\u662f\u7b2c k<\/code> \u4e2a\u4e0d\u540c\u7684\u5143\u7d20\u3002<\/p>\n

\u4f60\u5fc5\u987b\u8bbe\u8ba1\u5e76\u5b9e\u73b0\u65f6\u95f4\u590d\u6742\u5ea6\u4e3a O(n)<\/code> \u7684\u7b97\u6cd5\u89e3\u51b3\u6b64\u95ee\u9898\u3002<\/p>\n

\u793a\u4f8b 1:<\/strong><\/p>\n

\n

\u8f93\u5165: [3,2,1,5,6,4], k = 2
\n\u8f93\u51fa: 5<\/p>\n<\/blockquote>\n

\u793a\u4f8b 2:<\/strong><\/p>\n

\n

\u8f93\u5165: [3,2,3,1,2,4,5,5,6], k = 4
\n\u8f93\u51fa: 4<\/p>\n<\/blockquote>\n

\u9996\u5148\u60f3\u5230\u7684\u5f53\u7136\u662f\u5feb\u6392\u6765\u89e3\u51b3\uff0c\u6bcf\u6b21\u7f29\u5c0f\u67e5\u627e\u8303\u56f4\uff0c\u6700\u540e\u65f6\u95f4\u590d\u6742\u5ea6\u5c31\u662fO(n)<\/code>\u3002<\/p>\n

\u5b98\u65b9\u4ee3\u7801\uff1a<\/p>\n

class Solution {\n    int quickselect(int[] nums, int l, int r, int k) {\n        if (l == r) return nums[k];\n        int x = nums[l], i = l - 1, j = r + 1;\n        while (i < j) {\n            do i++; while (nums[i] < x);\n            do j--; while (nums[j] > x);\n            if (i < j){\n                int tmp = nums[i];\n                nums[i] = nums[j];\n                nums[j] = tmp;\n            }\n        }\n        if (k <= j) return quickselect(nums, l, j, k);\n        else return quickselect(nums, j + 1, r, k);\n    }\n    public int findKthLargest(int[] _nums, int k) {\n        int n = _nums.length;\n        return quickselect(_nums, 0, n - 1, n - k);\n    }\n}<\/code><\/pre>\n
\u4ee3\u7801\u5f88\u7b80\u6d01\uff0c\u4f46\u7ec6\u770b\u903b\u8f91\u8fd8\u662f\u6709\u70b9\u590d\u6742\uff0c\u8fd9\u6837\u5199\u7684\u5feb\u6392\u6709\u70b9\u96be\u4ee5\u7406\u89e3\uff0c\u4e0d\u8fc7\u7ecf\u8fc7\u6d4b\u8bd5\u901f\u5ea6\u786e\u5b9e\u5feb\uff0c\u4e0b\u9762\u662f\u6211\u81ea\u5df1\u5f88\u597d\u7406\u89e3\u7684\u5feb\u6392\uff1a<\/p>\n
class Solution {\n    int quickselect(int[] nums, int left, int right, int k) {\n        \/\/ \u8bb0\u5f55\u4e00\u4e0b\u5de6\u53f3\u8fb9\u754c\uff0c\u65b9\u4fbf\u9012\u5f52\n        int low = left;\n        int high = right;\n        int base = nums[left];\n        while(left < right){\n            \/\/ \u4ece\u53f3\u8fb9\u5f00\u59cb\uff0c\u5bfb\u627e\u7b2c\u4e00\u4e2a\u5c0f\u4e8e\u57fa\u51c6\u7684\u5143\u7d20\n            while (left < right && nums[right] >= base) {\n                right--;\n            }\n            nums[left] = nums[right];\n\n            \/\/ \u4ece\u5de6\u8fb9\u5f00\u59cb\uff0c\u5bfb\u627e\u7b2c\u4e00\u4e2a\u5927\u4e8e\u57fa\u51c6\u7684\u5143\u7d20\n            while (left < right && nums[left] <= base) {\n                left++;\n            }\n            nums[right] = nums[left];\n        }\n\n        \/\/ \u5c06\u57fa\u51c6\u5143\u7d20\u653e\u5230\u6700\u7ec8\u7684\u4f4d\u7f6e\u4e0a\n        nums[left] = base;\n\n        if(left == k){\n            return base;\n        }\n        \/\/ \u9012\u5f52\u5904\u7406\u5de6\u534a\u90e8\u5206\n        else if(left>k){\n            return quickselect(nums, low, left - 1,k);\n        }\n        \/\/ \u9012\u5f52\u5904\u7406\u53f3\u534a\u90e8\u5206\n        else{\n            return quickselect(nums, left + 1, high,k);\n        }\n    }\n    public int findKthLargest(int[] _nums, int k) {\n        int n = _nums.length;\n        return quickselect(_nums, 0, n - 1, n - k);\n    }\n}<\/code><\/pre>\n
\u8fd9\u4e2a\u5feb\u6392\u5c31\u6bd4\u8f83\u6e05\u6670\uff0c\u8ba4\u771f\u770b\u5e94\u8be5\u5c31\u80fd\u60f3\u901a\u3002<\/p>\n
\u53e6\u5916\u5c31\u662f\u4f7f\u7528\u5806\u6392\u5e8f\u4e86\uff0c\u5806\u6392\u5e8f\u867d\u7136\u65f6\u95f4\u590d\u6742\u5ea6\u662f\u9ad8\u4e86\u70b9O(nlogn)<\/code>\uff0c\u4f46\u8fd9\u9053\u9898\u8fd0\u884c\u8d77\u6765\u8fd8\u86ee\u5feb\u7684\u3002<\/p>\n
class Solution {\n    public int findKthLargest(int[] nums, int k) {\n        int heapSize = nums.length;\n        buildMaxHeap(nums, heapSize);\n        for (int i = nums.length - 1; i >= nums.length - k + 1; --i) {\n            swap(nums, 0, i);\n            --heapSize;\n            maxHeapify(nums, 0, heapSize);\n        }\n        return nums[0];\n    }\n\n    public void buildMaxHeap(int[] a, int heapSize) {\n        for (int i = heapSize \/ 2; i >= 0; --i) {\n            maxHeapify(a, i, heapSize);\n        } \n    }\n\n    public void maxHeapify(int[] a, int i, int heapSize) {\n        int l = i * 2 + 1, r = i * 2 + 2, largest = i;\n        if (l < heapSize && a[l] > a[largest]) {\n            largest = l;\n        } \n        if (r < heapSize && a[r] > a[largest]) {\n            largest = r;\n        }\n        if (largest != i) {\n            swap(a, i, largest);\n            maxHeapify(a, largest, heapSize);\n        }\n    }\n\n    public void swap(int[] a, int i, int j) {\n        int temp = a[i];\n        a[i] = a[j];\n        a[j] = temp;\n    }\n}\n<\/code><\/pre>\n
\u8fd0\u884c\u65f6\u95f4\u77ed\u7684\u539f\u56e0\u53ef\u80fd\u662f\u56e0\u4e3a\u6d4b\u8bd5\u7528\u4f8b\u4e2d\u7684k\u503c\u8f83\u5c0f\u3002<\/p>\n
\u5806\u6392\u5e8f\u8fd8\u662f\u633a\u91cd\u8981\u7684\uff0c\u8fd9\u91cc\u4f7f\u7528\u6570\u7ec4\u5b9e\u73b0\u7684\u65b9\u6cd5\u7279\u522b\u7ecf\u5178\uff0c\u53ef\u4ee5\u8ba4\u771f\u770b\u770b\u3002<\/p>\n","protected":false},"excerpt":{"rendered":"
\u6570\u7ec4\u4e2d\u7b2ck\u4e2a\u6700\u5927\u5143\u7d20 \u7ed9\u5b9a\u6574\u6570\u6570\u7ec4 nums \u548c\u6574\u6570 k\uff0c\u8bf7\u8fd4\u56de\u6570\u7ec4\u4e2d\u7b2c k \u4e2a\u6700\u5927\u7684\u5143\u7d20\u3002 \u8bf7\u6ce8\u610f\uff0c\u4f60\u9700\u8981\u627e\u7684\u662f\u6570\u7ec4\u6392\u5e8f\u540e\u7684\u7b2c  …<\/p>","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[1],"tags":[5,26,27,9],"class_list":["post-237","post","type-post","status-publish","format-standard","hentry","category-uncategorized","tag-java","tag-26","tag-27","tag-leetcode"],"_links":{"self":[{"href":"https:\/\/wangqianming.top\/index.php\/wp-json\/wp\/v2\/posts\/237","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/wangqianming.top\/index.php\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/wangqianming.top\/index.php\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/wangqianming.top\/index.php\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/wangqianming.top\/index.php\/wp-json\/wp\/v2\/comments?post=237"}],"version-history":[{"count":1,"href":"https:\/\/wangqianming.top\/index.php\/wp-json\/wp\/v2\/posts\/237\/revisions"}],"predecessor-version":[{"id":238,"href":"https:\/\/wangqianming.top\/index.php\/wp-json\/wp\/v2\/posts\/237\/revisions\/238"}],"wp:attachment":[{"href":"https:\/\/wangqianming.top\/index.php\/wp-json\/wp\/v2\/media?parent=237"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/wangqianming.top\/index.php\/wp-json\/wp\/v2\/categories?post=237"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/wangqianming.top\/index.php\/wp-json\/wp\/v2\/tags?post=237"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}