1.数组中的第Ｋ个最大元素No.215

• 方法一：NlogN不能满足时间复杂度的要求

java"> public int findKthLargest(int[] nums, int k) {Arrays.sort(nums);return nums[nums.length-k];}

• 方法二：快速排序 NlogN 不能满足时间复杂度的要求

java">public int findKthLargest(int[] nums, int k) {quick_sort(nums,0,nums.length-1);return nums[nums.length-k];}public void quick_sort(int[] nums,int l,int r){if(l>=r) return;int i = l-1;int j = r+1;int x = nums[l];while(i<j){do{i++;}while(nums[i]<x);do{j--;}while(nums[j]>x);if(i<j){int temp = nums[i];nums[i] = nums[j];nums[j] = temp;}}quick_sort(nums,l,j);quick_sort(nums,j+1,r);}

• 方法三：

java">class Solution {// 主函数，用于找到数组中第k大的元素public int findKthLargest(int[] nums, int k) {int n = nums.length;  // 获取数组长度return quick(nums, 0, n - 1, n - k);  // 调用快速选择算法，寻找第(n-k+1)小的元素，即第k大的元素}// 快速选择算法实现int quick(int[] a, int left, int right, int index) {int p = partition(a, left, right);  // 对数组进行划分，并返回枢轴位置if (p == index) {  // 如果枢轴位置正好是目标索引return a[p];  // 返回该位置的元素值}if (p < index) {  // 如果目标索引在枢轴右侧return quick(a, p + 1, right, index);  // 在右子区间继续查找} else {  // 如果目标索引在枢轴左侧return quick(a, left, p - 1, index);  // 在左子区间继续查找}}// 划分函数，使用随机选择的枢轴进行划分int partition(int[] a, int left, int right) {int idx = ThreadLocalRandom.current().nextInt(right - left + 1) + left;  // 随机选择一个枢轴位置swap(a, left, idx);  // 将枢轴放到最左边int pv = a[left];  // 取出枢轴值int i = left + 1;  // 初始化左侧指针int j = right;  // 初始化右侧指针while (i <= j) {  // 当左右指针未交错时while (i <= j && a[i] < pv) {  // 左侧找比枢轴大的i++;}while (i <= j && a[j] > pv) {  // 右侧找比枢轴小的j--;}if (i <= j) {  // 如果找到了一对可以交换的元素swap(a, i, j);  // 交换这对元素i++;  // 移动左侧指针j--;  // 移动右侧指针}}swap(a, j, left);  // 将枢轴放回正确的位置return j;  // 返回枢轴的新位置}// 交换数组中的两个元素void swap(int[] a, int i, int j) {int t = a[i];  // 暂存一个元素a[i] = a[j];  // 交换操作a[j] = t;}
}

• I like

java">import java.util.Random;class Solution {public int findKthLargest(int[] nums, int k) {int n = nums.length;int target = n - k;  // 因为要找第 k 大元素，等价于找第 n-k 小元素int l = 0, r = n - 1;while (l <= r) {int pIndex = partition(nums, l, r);  // 划分后的枢轴位置if (pIndex == target) {return nums[pIndex];  // 找到目标元素} else if (pIndex < target) {l = pIndex + 1;  // 目标元素在右半部分} else {r = pIndex - 1;  // 目标元素在左半部分}}return -1;  // 理论上应该不会到这里，保证数组一定有效}public int partition(int[] nums, int l, int r) {Random random = new Random();int idx = random.nextInt(r - l + 1) + l;  // 随机选择枢轴swap(nums, l, idx);  // 将枢轴放到数组的最左边int x = nums[l];  // 取出枢轴值int i = l + 1;  // 左侧指针int j = r;      // 右侧指针while (i <= j) {while (i <= j && nums[i] < x) {  // 左侧找比枢轴大的i++;}while (i <= j && nums[j] > x) {  // 右侧找比枢轴小的j--;}if (i <= j) {swap(nums, i, j);  // 交换不符合条件的元素i++;j--;}}swap(nums, l, j);  // 将枢轴放到正确位置return j;  // 返回枢轴的位置}// 交换数组中的两个元素public void swap(int[] nums, int x, int y) {int temp = nums[x];nums[x] = nums[y];nums[y] = temp;}
}

2.前K个高频元素347

• 桶排序

java">class Solution {public int[] topKFrequent(int[] nums, int k) {// 创建一个hashmap，并统计每个元素的频率HashMap<Integer, Integer> map = new HashMap<>();for (int num : nums) {map.put(num, map.getOrDefault(num, 0) + 1);}// 创建桶数组，桶的索引表示元素的频率，桶中的元素是具有相同频率的数字List<Integer>[] bucket = new List[nums.length + 1];for (int i = 0; i < bucket.length; i++) {bucket[i] = new ArrayList<>();}// 将频率存入桶中for (Map.Entry<Integer, Integer> entry : map.entrySet()) {bucket[entry.getValue()].add(entry.getKey());}// 从桶中提取前 k 个频率最高的元素int[] res = new int[k];int index = 0;for (int i = bucket.length - 1; i >= 0 && index < k; i--) {for (int num : bucket[i]) {res[index++] = num;if (index == k) {break; // 找到 k 个元素后退出}}}return res;}
}