1、查找第K大元素？

  • 思想： 分而治之
  • 算法： 归并排序



步骤：

1、1个退出条件 2个递归调用(左和右)

2、1个合并，合并中 4个循环(1 去最后元素， 取左边剩余元素， 取右边剩余元素 复制) 

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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
public void findKthLargest(int[] arr, int k){
   
   //归并排序
   mergeSort(arr, 0, arr.length - 1);
   //返回第K大元素
  return arr[arr.length - k];
}


public void mergeSort(int[] arr, int left, int right){
  
  //退出条件
  if(left >= right){
    return;
  }
  
  //分解
  int mid = (left + right) / 2;
  //left
  mergeSort(arr, left, mid);
  //rigth
  mergeSort(arr, mid + 1, right);
  
  //合并
  merge(arr, left, mid, right);
}

public void merge(int[] arr, int left , int mid, int right){
  	
   int i = left;
   int j = mid + 1;
   int k = 0;
   //temp
   int[] temp = new int[right - left + 1];  
  //取最后的元素
   while(i <= mid && j <= right){
      if(arr[i] > arr[j]){
         temp[k++] = arr[j++];
      }else{
         temp[k++] = arr[i++];
      }
   }
   
  //取剩余的元素
  while(i <= mid){
     temp[k++] = arr[i++];
  }
  while(j <= right){
     temp[k++] = arr[j++];
  }
  
  //复制
  k = 0;
  while(left <= right){
    arr[left++] = temp[++];
  }
}

  • 运行结果