leetCode215

秒速五厘米 2022-01-23 05:09 143阅读 0赞

在未排序的数组中找到第 **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

思路：

1.直接调用api,取n-k个位置就好。

2. 拿Java的优先级队列，重写Comparator o2-o1即可，new PriorityQueue<>(new Comparator<Integer>()\{

@Override

public int compare(Integer o1,Integer o2)\{

return o2-o1;

\});

以上2种以第一种时间复杂度最快。

3.利用快速排序的思想，稍微改造。

利用快速排序思想，对数组进行划分，并且判断划分的边界元素位置mid是否为第k大的数(k - 1)； 若是则返回该数，若mid > k - 1说明第k大的数在左半边数组里；若mid < k - 1说明在右半边数组里。对其继续进行数组划分，直到找到第k大的数。 数组划分函数partation采用数组中心位置的元素值作为bound（边界），也可以采用随机元素，最好不要用第一个（最后一个）元素，防止数组绝大部分元素是有序的，影响查找效率。

class Solution {
    public:
       int findKthLargest(vector<int>& nums, int k) {
           int low = 0, high = nums.size() - 1, mid = 0;
           while (low <= high) {
               mid = partation(nums, low, high);
               if (mid == k - 1) return nums[mid];
               else if (mid > k - 1) high = mid - 1;
               else low = mid + 1;
           }
           //  实际上返回 -1 代表没有第 k 大的数，这里不存在
           return -1;
       }
       
       int partation(vector<int>& nums, int low, int high) {
           int left = low + 1, right = high;
           swap(nums[low], nums[(low + high) / 2]);
           int bound = nums[low];
           //  双指针，快速排序，交换不符合条件的数据
           while (left <= right) {
               while (left < high && nums[left] >= bound) left++;
               while (nums[right] < bound) right--;
               if (left < right) 
                   swap(nums[left++], nums[right--]);
               else break;
           }
           //  将bound放到换分完成后的两个数组之间，作为边界, 返回bound的位次
           swap(nums[low], nums[right]);
           return right;
       }
    };