用堆实现第k大元素

除了使用传统的各种排序方法找到第k大元素外，尝试了用堆实现，相当于一次逻辑思维的探索，分别用java和golang试了试,heapfiy函数是用来处理只有一个三个元素组成的小堆是乱的，其他都不乱的，而build_heap是用来处理整堆得，从右向左，从下向上:

代码语言：javascript复制

class Solution {
    public void swap(int[] heap,int i,int j){
        int tmp = heap[i];
        heap[i] = heap[j];
        heap[j] = tmp;
    }
    public void heapify(int[] heap,int n,int i){
        if(i>=n){
            return;
        }
        int c1 = i*2 1;
        int c2 = i*2 2;
        int max = i;
        
        if(c1<=n-1&&heap[c1]>heap[i]){
            max = c1;
        }
        if(c2<=n-1&&heap[c2]>heap[i]&&heap[c2]>heap[c1]){
            max=c2;
        }
        if(max!=i){
           swap(heap,max,i);
           heapify(heap,n,max);
        }
        
        // return heap;
    }
    public void build_heap(int[] heap,int n){//整体堆创建，从右向左，从下向上
         int last_node = n-1;
         int parent = (last_node-1) / 2;
         int i;
         for(i=parent;i>=0;i--){
              heapify(heap,n,i);
         }
         
    }
    public int findKthLargest(int[] nums, int k) {
        if (nums.length ==0){
            throw new RuntimeException("数据有误");
        }
        Integer res = null;
        int n = nums.length;
        build_heap(nums,n);
        for(int i =n-1; i>=n-k; i--){
           swap(nums,0,i);
            res = nums[i];
            heapify(nums,i,0);//相当于截断，不要最后一个元素
        }
        return res ;
    }
}

代码语言：javascript复制

func swap(heap []int,i int,j int){
    tmp := heap[i]
    heap[i] = heap[j]
    heap[j] = tmp
}
func heapify(heap []int,i int,n int){
    if i>=n{
      return
    }
    c1:=i*2 1
    c2:=i*2 2
    max := i
    if(c1<=n-1&&heap[c1]>heap[i]){
        max = c1
    }
    if(c2<=n-1&&heap[c2]>heap[i]&&heap[c2]>heap[c1]){
        max = c2
    }
    if(max!=i){
        swap(heap,max,i)
        heapify(heap,max,n)
    }
}

func build_heap(heap []int,n int){
    last_node := n-1
    parent := (last_node-1) / 2
    for i:=parent;i>=0;i-- {
       heapify(heap,i,n)
    }
}
func findKthLargest(nums []int, k int) int {
      var res int
      n:=len(nums)
      build_heap(nums,n)
      for i:=n-1;i>=n-k;i-- {
          swap(nums,0,i)
          res = nums[i]
          heapify(nums,0,i)
      }
      return res
}

再附加一个队列方法,取了个巧:

代码语言：javascript复制

class Solution {
   
    public int findKthLargest(int[] nums, int k) {
       PriorityQueue<Integer> pq = new PriorityQueue<>();
       for(int val:nums){
           pq.add(val);
           if(pq.size()>k){
               pq.poll();
           }
       }
       return pq.poll();
    }
}

附快排实现:

代码语言：javascript复制

class Solution {
    public void swap(int[] heap,int i,int j){
        int tmp = heap[i];
        heap[i] = heap[j];
        heap[j] = tmp;
    }
     public  void quickSort(int[] arr,int L,int R){
   if(L<R){
     //随机找一个值和最后一个值交换
     swap(arr,L (int)(Math.random()*(R-L 1)),R);
     int[] p = partition(arr,L,R);
     quickSort(arr,L,p[0]-1);//<区
     quickSort(arr,p[1] 1,R);//>区
     }
   }
  public  int[] partition(int[] arr,int L,int R){
    int less = L - 1; //<区右边界
    int more = R; //>区左边界
    while(L<more){
    //如果[i]<num,[i]和<区下一个交换,<区右扩i  
    if(arr[L] < arr[R]){
        swap(arr,  less,L  );
     }else if(arr[L]>arr[R]){  //[i]>num.[i]和>区的前一个做交换.>区左扩，i原地不变
     swap(arr,--more,L);
     }else{
     //[i]==num,直接跳下一个
      L  ;
      }
  }
  //>区的第一个数和最后一个数做交换
  swap(arr,more,R);
  return new int[]{ less   1, more };
}

    public int findKthLargest(int[] nums, int k) {
             quickSort(nums,0,nums.length-1);
             return nums[nums.length-k];
    }
}

java build heap 队列 排序

0 人点赞