速い列と速い列の思想を利用して配列のK番目の大きい数を探します

1493 ワード

問題:速い列の思想を利用して1つの配列の中でK番目に大きい数を探します.
構想:速い列の中で1つの戻りの第1の数字を呼び出して配列を2つの部分の後の1つの下の札に分けて、この下の札はこの第1の数字が並べ替えた後の位置を表して、私達はそれをKと比較することを通じて、毎回2つの部分の1つだけを選んで再帰的なクエリーを行うことができます.
ここで速い列の分治思想を利用してK番目の大きい数を探すときは重くない、例えば1、2、3、3、5番目の大きいと3番目の大きいはすべて3で、4番目の大きいのは2である.
Javaコード:Java/**Created with IntelliJ IDEA.
  • User: hqtc
  • Date: 16-3-22
  • Time:午後9:52
  • To change this template use File | Settings | File Templates. */public class QuickSort{ private int getSeparatorIndex(int[] nums, int low, int high) { int k = nums[low]; while (low < high) { while (k < nums[high] && low < high) { high--; } if (low < high) nums[low++] = nums[high]; while (k > nums[low] && low < high) { low++; } if (low < high) nums[high--] = nums[low]; } nums[low] = k; return low; } public void sort(int num[], int low, int high) { if (low < high) { int sepIndex = getSeparatorIndex(num, low, high); sort(num, low, sepIndex - 1); sort(num, sepIndex + 1, high); } } public int findKthMax(int arr[], int k, int left, int right) { int sepIndex = getSeparatorIndex(arr, left, right); if (k == arr.length - sepIndex) { return arr[sepIndex]; } else { if (k > arr.length - sepIndex) { return findKthMax(arr, k, left, sepIndex - 1); } else { return findKthMax(arr, k, sepIndex + 1, right); } } } }