雖然更多用的是桶
數組中的第k個最大元素(215)
桶排序
class Solution {
public int findKthLargest(int[] nums, int k) {
int[] buckets = new int[200001];
for (int i = 0; i < nums.length; i++){
buckets[nums[i]+10000]++;
}
for (int i = 20000; i >= 0; i--){
k -= buckets[i];
if (k <= 0){
return i - 10000;
}
}
return 0;
}
}
選擇排序
class Solution {
public int findKthLargest(int[] nums, int k) {
List<Integer> numList = new ArrayList<>();
for (int num : nums){
numList.add(num);
}
return quickSelect(numList, k);
}
private int quickSelect(List<Integer> nums, int k){
Random rand = new Random();
int midd = nums.get(rand.nextInt(nums.size()));
List<Integer> big = new ArrayList<>();
List<Integer> sma = new ArrayList<>();
for (int num : nums){
if (num > midd){
big.add(num);
}
else if (num < midd){
sma.add(num);
}
}
if (k <= big.size()) return quickSelect(big, k);
else if (nums.size() < k + sma.size()) return quickSelect(sma, k + sma.size() - nums.size());
return midd;
}
}
- 分析
桶排序
nums[i] 只有 10?, 便毅然決然的打表了 ?? , 很壞啊擊敗了90%
選擇排序
隨機選擇數組中的一個數作為中軸, 通過比較k落在中軸左端還是右端, 進一步縮小范圍
前k個高頻元素
class Solution {
public int[] topKFrequent(int[] nums, int k) {
int n = nums.length;
Map<Integer, Integer> num_buckets = new HashMap<>();
for (int num : nums){
num_buckets.merge(num, 1, Integer::sum);
}
int max_nums = Collections.max(num_buckets.values());
List<Integer>[] freq_buckets = new ArrayList[max_nums+1];
Arrays.setAll(freq_buckets, i -> new ArrayList<>());
for (Map.Entry<Integer, Integer> entry : num_buckets.entrySet){
freq_buckets[entry.getValue()].add(entry.getKey());
}
int[] res = new int[k];
int count = 0;
for (int i = max_nums; count < k && i >= 0; i--){
for (int num : freq_buckets[i]) res[count++] = num;
}
return res;
}
}
- 分析
以每個<整數>分桶, 再以<頻率>對整數分桶
選擇 hash而不是 int[] → 元素重復數量大
數據流的中位數(295)
class MedianFinder {
private PriorityQueue<Integer> lef = new PriorityQueue<>((a,b) -> b-a); //大堆
private PriorityQueue<Integer> rig = new PriorityQueue<>(); //小堆
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;
}
}
- 分析
排序部分 - > addNum先在對端排序, 取出對端的 最小\最大 值
取中位數部分- > 當總數為奇數時, 以lef.peek()作為中位數, 需要保持 lef.size() ≥ rig.size()
浙公網安備 33010602011771號