计算机科学基础leetcode刷题数组
,
Source
Edit
History

215. 数组中的第K个最大元素

Problem: 215. 数组中的第K个最大元素

快排

这里的快排的交换是用的挖坑的算法,举例子如下:

解题方法

快排:

  • 判断左小于右边
        - 左右指针ij,随机数最左边的数 x = nums[i]
        - 遍历当 i < j
            - 从右往左大于x
                - j–
            - 如果i < j
                - num[i] = num[j];
                - i++;
            - 从左往右小于x
                - i++
            - 如果i < j
                - nums[j] = num[i]
                - j–;
        nums[i] = x;
        递归(nums,left,i-1);    
        递归(nums,i+1,right);

   

复杂度

时间复杂度:

添加时间复杂度, 示例： $O(n)$

空间复杂度:

添加空间复杂度, 示例： $O(n)$

Code

[]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
public class Solution {
    public int FindKthLargest(int[] nums, int k) {
        int n = nums.Length;
        QuickSort(nums,0,nums.Length-1);
        return nums[nums.Length - k];
    }

    public void QuickSort(int[] nums,int left,int right){
        if(left<right) {
            int i,j,x;
            i = left;
            j = right;
            x = nums[i];
            while(i<j){
                while(i < j &&  nums[j] > x) j--;
                if(i<j) nums[i++] = nums[j];
                while(i < j &&  nums[i] < x) i++;
                if(i<j) nums[j--] = nums[i];
            }
            nums[i] = x;
            QuickSort(nums,left,i-1);
            QuickSort(nums,i+1,right);
        }
    }
}