首页 › Java论坛 › hot100之堆

就图一乐儿 發表於 2025-6-21 12:01:00

hot100之堆

<blockquote>
<p>虽然更多用的是桶</p>
</blockquote>
<h3 id="数组中的第k个最大元素215">数组中的第k个最大元素(215)</h3>
<p><strong>桶排序</strong></p>
<pre><code class="language-java">class Solution {
    public int findKthLargest(int[] nums, int k) {
      int[] buckets = new int;
      for (int i = 0; i &lt; nums.length; i++){
            buckets+10000]++;
      }
      for (int i = 20000; i &gt;= 0; i--){
            k -= buckets;
            if (k &lt;= 0){
                return i - 10000;
            }
      }
      return 0;
    }
}
</code></pre>
<p><strong>选择排序</strong></p>
<pre><code class="language-java">class Solution {
    public int findKthLargest(int[] nums, int k) {
      List&lt;Integer&gt; numList = new ArrayList&lt;&gt;();
      for (int num : nums){
            numList.add(num);
      }
      return quickSelect(numList, k);
    }

    private int quickSelect(List&lt;Integer&gt; nums, int k){
      Random rand = new Random();
      int midd = nums.get(rand.nextInt(nums.size()));

      List&lt;Integer&gt; big = new ArrayList&lt;&gt;();
      List&lt;Integer&gt; sma = new ArrayList&lt;&gt;();

      for (int num : nums){
            if (num &gt; midd){
                big.add(num);
            }
            else if (num &lt; midd){
                sma.add(num);
            }
      }

      if (k &lt;= big.size()) return quickSelect(big, k);
      else if (nums.size() &lt; k + sma.size()) return quickSelect(sma, k+ sma.size() - nums.size());
      return midd;
    }
}
</code></pre>
<ul>
<li>分析</li>
</ul>
<p><strong>桶排序</strong></p>
<p><code>nums</code> 只有 10⁴, 便毅然决然的打表了 🤣 , 很坏啊击败了90%</p>
<p><strong>选择排序</strong></p>
<p>随机选择数组中的一个数作为中轴, 通过比较k落在中轴左端还是右端, 进一步缩小范围</p>
<h3 id="前k个高频元素">前k个高频元素</h3>
<pre><code class="language-java">class Solution {
    public int[] topKFrequent(int[] nums, int k) {
      int n = nums.length;
      Map&lt;Integer, Integer&gt; num_buckets = new HashMap&lt;&gt;();
      for (int num : nums){
            num_buckets.merge(num, 1, Integer::sum);
      }
      int max_nums = Collections.max(num_buckets.values());

      List&lt;Integer&gt;[] freq_buckets = new ArrayList;
      Arrays.setAll(freq_buckets, i -&gt; new ArrayList&lt;&gt;());
      for (Map.Entry&lt;Integer, Integer&gt; entry : num_buckets.entrySet){
            freq_buckets.add(entry.getKey());
      }

      int[] res = new int;
      int count = 0;
      for (int i = max_nums; count &lt; k &amp;&amp; i &gt;= 0; i--){
            for (int num : freq_buckets) res = num;
      }

      return res;
    }
}
</code></pre>
<ul>
<li>分析</li>
</ul>
<p>以每个&lt;整数&gt;分桶, 再以&lt;频率&gt;对整数分桶</p>
<blockquote>
<p>选择 hash而不是 int[]→ 元素重复数量大</p>
</blockquote>
<h3 id="数据流的中位数295">数据流的中位数(295)</h3>
<pre><code class="language-java">class MedianFinder {
    private PriorityQueue&lt;Integer&gt; lef = new PriorityQueue&lt;&gt;((a,b) -&gt; b-a); //大堆
    private PriorityQueue&lt;Integer&gt; rig = new PriorityQueue&lt;&gt;();    //小堆

    public MedianFinder() {
    }
   
    public void addNum(int num) {
      if(lef.size() == rig.size()){
            rig.offer(num);
            lef.offer(rig.poll());      
      }else{
            lef.offer(num);
            rig.offer(lef.poll());
      }
    }
   
    public double findMedian() {
      if (lef.size() != rig.size()){
            return lef.peek();
      }
      return (lef.peek() + rig.peek()) / 2.0;
    }
}

</code></pre>
<ul>
<li>分析</li>
</ul>
<p>排序部分 - &gt; <code>addNum</code>先在对端排序, 取出对端的 最小\最大 值</p>
<p>取中位数部分- &gt; 当总数为奇数时, 以<code>lef.peek()</code>作为中位数, 需要保持 <code>lef.size() ≥ rig.size()</code></p><br><br>
来源：https://www.cnblogs.com/many-bucket/p/18939842

查看完整版本: hot100之堆