Your Site Title

Leetcode - 排序

 
  • May 14, 2020

第K大的元素

调库

public int findKthLargest(int[] nums, int k) {
    List<Integer> collect = Arrays.stream(nums).boxed().sorted((num1, num2) -> num2 - num1).collect(Collectors.toList());
    return collect.get(k-1);
}

选择排序

 public int findKthLargest(int[] nums, int k) {
     for (int i=0; i<k; i++){
         int max=-1, index=i;
         for (int j=i; j<nums.length; j++){
             if (nums[j] > max){
                 max = nums[j];
                 index = j;
             }
         }
         nums[index] = nums[i];
         nums[i] = max;
     }
     return nums[k-1];
 }

堆排序 - 完全排序。改进：通过堆维护一个Ksize的大值优先队列，有较大值时删掉最小值，放入最大值。怎么实现？

class Solution {
    public void heapSort(int[] tree){
        buildHeap(tree);
        int n = tree.length-1;
        for(int i=n; i>=0; i--){
            swap(tree, 0, i);
            heapify(tree, i, 0);
        }
    }
    public void buildHeap(int[] tree){
        int n = (tree.length-1) / 2;
        for(int i=n; i>=0; i--) 
            heapify(tree, tree.length, i);
    }
    public void swap(int[] arr, int i, int j){
        int t = arr[i];
        arr[i] = arr[j];
        arr[j] = t;
    }
    public void heapify(int[] tree, int n, int i){
        int c1=i*2+1, c2=i*2+2, max=i;
        if(c1<n && tree[c1]>tree[max]) max=c1;
        if(c2<n && tree[c2]>tree[max]) max=c2;
        if(max != i){
            swap(tree, i, max);
            heapify(tree, n, max);
        }
    }
    public int findKthLargest(int[] nums, int k) {
        heapSort(nums);
        return nums[nums.length-k];
    }
}

快速选择排序1，利用了快排的分治思想

public int findKthLargest(int[] nums, int k) {
    k = nums.length - k;
    int lo = 0;
    int hi = nums.length - 1;
    while (lo < hi) {
        final int j = partition(nums, lo, hi);
        if(j < k) {
            lo = j + 1;
        } else if (j > k) {
            hi = j - 1;
        } else {
            break;
        }
    }
    return nums[k];
}
private int partition(int[] a, int lo, int hi) {
    int i = lo;
    int j = hi + 1;
    while(true) {
        while(i < hi && less(a[++i], a[lo]));
        while(j > lo && less(a[lo], a[--j]));
        if(i >= j) {
            break;
        }
        exch(a, i, j);
    }
    exch(a, lo, j);
    System.out.println(Arrays.toString(a));
    return j;
}

private void exch(int[] a, int i, int j) {
    final int tmp = a[i];
    a[i] = a[j];
    a[j] = tmp;
}

private boolean less(int v, int w) {
    return v < w;
}

快速选择排序2

public int findKthLargest(int[] A, int k) {
    k = A.length - k; // convert to index of k largest
    int l = 0, r = A.length - 1;
    while (l <= r) {
        int i = l; // partition [l,r] by A[l]: [l,i]<A[l], [i+1,j)>=A[l]
        for (int j = l + 1; j <= r; j++)
            if (A[j] < A[l]) swap(A, j, ++i);
        swap(A, l, i);

        if (k < i) r = i - 1;
        else if (k > i) l = i + 1;
        else return A[i];
    }
    return -1; // k is invalid
}

出现频率最多的 k 个元素

Search