<ruby id="bdb3f"></ruby>

    <p id="bdb3f"><cite id="bdb3f"></cite></p>

      <p id="bdb3f"><cite id="bdb3f"><th id="bdb3f"></th></cite></p><p id="bdb3f"></p>
        <p id="bdb3f"><cite id="bdb3f"></cite></p>

          <pre id="bdb3f"></pre>
          <pre id="bdb3f"><del id="bdb3f"><thead id="bdb3f"></thead></del></pre>

          <ruby id="bdb3f"><mark id="bdb3f"></mark></ruby><ruby id="bdb3f"></ruby>
          <pre id="bdb3f"><pre id="bdb3f"><mark id="bdb3f"></mark></pre></pre><output id="bdb3f"></output><p id="bdb3f"></p><p id="bdb3f"></p>

          <pre id="bdb3f"><del id="bdb3f"><progress id="bdb3f"></progress></del></pre>

                <ruby id="bdb3f"></ruby>

                ??一站式輕松地調用各大LLM模型接口,支持GPT4、智譜、豆包、星火、月之暗面及文生圖、文生視頻 廣告
                # 0215. 數組中的第K個最大元素 ## 題目地址(215. 數組中的第K個最大元素) <https://leetcode-cn.com/problems/kth-largest-element-in-an-array/> ## 題目描述 ``` <pre class="calibre18">``` 在未排序的數組中找到第 k 個最大的元素。請注意,你需要找的是數組排序后的第 k 個最大的元素,而不是第 k 個不同的元素。 示例 1: 輸入: [3,2,1,5,6,4] 和 k = 2 輸出: 5 示例 2: 輸入: [3,2,3,1,2,4,5,5,6] 和 k = 4 輸出: 4 說明: 你可以假設 k 總是有效的,且 1 ≤ k ≤ 數組的長度。 ``` ``` ## 前置知識 - 堆 - Quick Select ## 公司 - 阿里 - 騰訊 - 百度 - 字節 ## 思路 這道題要求在一個無序的數組中,返回第K大的數。根據時間復雜度不同,這題有3種不同的解法。 #### 解法一 (排序) 很直觀的解法就是給數組排序,這樣求解第`K`大的數,就等于是從小到大排好序的數組的第`(n-K)`小的數 (n 是數組的長度)。 例如: ``` <pre class="calibre18">``` [3,2,1,5,6,4], k = 2 1. 數組排序: [1,2,3,4,5,6], 2. 找第(n-k)小的數 n-k=4, nums[4]=5 (第2大的數) ``` ``` *時間復雜度:*`O(nlogn) - n 是數組長度。` #### 解法二 - 小頂堆(Heap) 可以維護一個大小為`K`的小頂堆,堆頂是最小元素,當堆的`size > K` 的時候,刪除堆頂元素. 掃描一遍數組,最后堆頂就是第`K`大的元素。 直接返回。 例如: ![](https://img.kancloud.cn/cf/77/cf772edcbe871b87bbe071570c0c851d_1394x1080.jpg) *時間復雜度*:`O(n * logk) , n is array length`*空間復雜度*:`O(k)` 跟排序相比,以空間換時間。 #### 解法三 - Quick Select Quick Select 類似快排,選取pivot,把小于pivot的元素都移到pivot之前,這樣pivot所在位置就是第pivot index 小的元素。 但是不需要完全給數組排序,只要找到當前pivot的位置是否是在第(n-k)小的位置,如果是,找到第k大的數直接返回。 具體步驟: ``` <pre class="calibre18">``` 1. 在數組區間隨機取`pivot index = left + random[right-left]`. 2. 根據pivot 做 partition,在數組區間,把小于pivot的數都移到pivot左邊。 3. 得到pivot的位置 index,`compare(index, (n-k))`. a. index == n-k -> 找到第`k`大元素,直接返回結果。 b. index < n-k -> 說明在`index`右邊,繼續找數組區間`[index+1, right]` c. index > n-k -> 那么第`k`大數在`index`左邊,繼續查找數組區間`[left, index-1]`. 例子,【3,2,3,1,2,4,5,5,6], k = 4 如下圖: ``` ``` ![](https://img.kancloud.cn/00/3d/003d4c733496a1c446c6112fe1af52a9_1245x861.jpg) *時間復雜度*: - 平均是:`O(n)` - 最壞的情況是:`O(n * n)` ## 關鍵點分析 1. 直接排序很簡單 2. 堆(Heap)主要是要維護一個K大小的小頂堆,掃描一遍數組,最后堆頂元素即是所求。 3. Quick Select, 關鍵是是取pivot,對數組區間做partition,比較pivot的位置,類似二分,取pivot左邊或右邊繼續遞歸查找。 ## 代碼(Java code) *解法一 - 排序* ``` <pre class="calibre18">``` <span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">KthLargestElementSort</span> </span>{ <span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-keyword">int</span> <span class="hljs-title">findKthlargest2</span><span class="hljs-params">(<span class="hljs-keyword">int</span>[] nums, <span class="hljs-keyword">int</span> k)</span> </span>{ Arrays.sort(nums); <span class="hljs-keyword">return</span> nums[nums.length - k]; } } ``` ``` *解法二 - Heap (PriorityQueue)* ``` <pre class="calibre18">``` <span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">KthLargestElementHeap</span> </span>{ <span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-keyword">int</span> <span class="hljs-title">findKthLargest</span><span class="hljs-params">(<span class="hljs-keyword">int</span>[] nums, <span class="hljs-keyword">int</span> k)</span> </span>{ PriorityQueue<Integer> pq = <span class="hljs-keyword">new</span> PriorityQueue<>(); <span class="hljs-keyword">for</span> (<span class="hljs-keyword">int</span> num : nums) { pq.offer(num); <span class="hljs-keyword">if</span> (pq.size() > k) { pq.poll(); } } <span class="hljs-keyword">return</span> pq.poll(); } } ``` ``` *解法三 - Quick Select* ``` <pre class="calibre18">``` <span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">KthLargestElementQuickSelect</span> </span>{ <span class="hljs-keyword">static</span> Random random = <span class="hljs-keyword">new</span> Random(); <span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-keyword">int</span> <span class="hljs-title">findKthLargest3</span><span class="hljs-params">(<span class="hljs-keyword">int</span>[] nums, <span class="hljs-keyword">int</span> k)</span> </span>{ <span class="hljs-keyword">int</span> len = nums.length; <span class="hljs-keyword">return</span> select(nums, <span class="hljs-params">0</span>, len - <span class="hljs-params">1</span>, len - k); } <span class="hljs-function"><span class="hljs-keyword">private</span> <span class="hljs-keyword">int</span> <span class="hljs-title">select</span><span class="hljs-params">(<span class="hljs-keyword">int</span>[] nums, <span class="hljs-keyword">int</span> left, <span class="hljs-keyword">int</span> right, <span class="hljs-keyword">int</span> k)</span> </span>{ <span class="hljs-keyword">if</span> (left == right) <span class="hljs-keyword">return</span> nums[left]; <span class="hljs-title">// random select pivotIndex between left and right</span> <span class="hljs-keyword">int</span> pivotIndex = left + random.nextInt(right - left); <span class="hljs-title">// do partition, move smaller than pivot number into pivot left</span> <span class="hljs-keyword">int</span> pos = partition(nums, left, right, pivotIndex); <span class="hljs-keyword">if</span> (pos == k) { <span class="hljs-keyword">return</span> nums[pos]; } <span class="hljs-keyword">else</span> <span class="hljs-keyword">if</span> (pos > k) { <span class="hljs-keyword">return</span> select(nums, left, pos - <span class="hljs-params">1</span>, k); } <span class="hljs-keyword">else</span> { <span class="hljs-keyword">return</span> select(nums, pos + <span class="hljs-params">1</span>, right, k); } } <span class="hljs-function"><span class="hljs-keyword">private</span> <span class="hljs-keyword">int</span> <span class="hljs-title">partition</span><span class="hljs-params">(<span class="hljs-keyword">int</span>[] nums, <span class="hljs-keyword">int</span> left, <span class="hljs-keyword">int</span> right, <span class="hljs-keyword">int</span> pivotIndex)</span> </span>{ <span class="hljs-keyword">int</span> pivot = nums[pivotIndex]; <span class="hljs-title">// move pivot to end</span> swap(nums, right, pivotIndex); <span class="hljs-keyword">int</span> pos = left; <span class="hljs-title">// move smaller num to pivot left</span> <span class="hljs-keyword">for</span> (<span class="hljs-keyword">int</span> i = left; i <= right; i++) { <span class="hljs-keyword">if</span> (nums[i] < pivot) { swap(nums, pos++, i); } } <span class="hljs-title">// move pivot to original place</span> swap(nums, right, pos); <span class="hljs-keyword">return</span> pos; } <span class="hljs-function"><span class="hljs-keyword">private</span> <span class="hljs-keyword">void</span> <span class="hljs-title">swap</span><span class="hljs-params">(<span class="hljs-keyword">int</span>[] nums, <span class="hljs-keyword">int</span> i, <span class="hljs-keyword">int</span> j)</span> </span>{ <span class="hljs-keyword">int</span> tmp = nums[i]; nums[i] = nums[j]; nums[j] = tmp; } } ``` ``` ## 參考(References) 1. [Quick Select Wiki](https://en.wikipedia.org/wiki/Quickselect)
                  <ruby id="bdb3f"></ruby>

                  <p id="bdb3f"><cite id="bdb3f"></cite></p>

                    <p id="bdb3f"><cite id="bdb3f"><th id="bdb3f"></th></cite></p><p id="bdb3f"></p>
                      <p id="bdb3f"><cite id="bdb3f"></cite></p>

                        <pre id="bdb3f"></pre>
                        <pre id="bdb3f"><del id="bdb3f"><thead id="bdb3f"></thead></del></pre>

                        <ruby id="bdb3f"><mark id="bdb3f"></mark></ruby><ruby id="bdb3f"></ruby>
                        <pre id="bdb3f"><pre id="bdb3f"><mark id="bdb3f"></mark></pre></pre><output id="bdb3f"></output><p id="bdb3f"></p><p id="bdb3f"></p>

                        <pre id="bdb3f"><del id="bdb3f"><progress id="bdb3f"></progress></del></pre>

                              <ruby id="bdb3f"></ruby>

                              哎呀哎呀视频在线观看