## 寻找最大的K个数（二）：快排优化和二分搜索 顶原

zongjh

（总要更好的，等你去发现）

Sb数组的长度。

package com.xylx.utils.selectK;

/**

* 优化快速排序，查找最大的Ｋ个输

*/

public class OptQuickSortSelectK {

public static void main(String[] args) {

int[] arr = Constans.getLengthArr(100);

System.out.println("排序前：");

Constans.printArr(arr);

optQuickSort(arr, 0, arr.length-1, Constans.K);

System.out.println("排序后:");

Constans.printArr(arr);

System.out.println("排序是否正确: "+Constans.isOk(arr));

Constans.selectK(arr);

}

public static void optQuickSort(int[] arr, int start, int end, int k) {

int left = start;

int right = end;

int key = arr[left];

while (left < right) {

while (left<right && arr[right] > key) {

right --;

}

if (left < right) {

int tmp = arr[left];

arr[left] = arr[right];

arr[right] = tmp;

left ++;

}

while (left<right && arr[left] < key) {

left ++;

}

if (left < right) {

int tmp = arr[right];

arr[right] = arr[left];

arr[left] = tmp;

right--;

}

}

if (start < left-1) {

int rightLength = end - right + 1;

System.out.println("rightLength="+rightLength+"  k="+k);

if (rightLength < k) { //右边数组小于需要的Ｋ数

optQuickSort(arr, start, left-1, k-rightLength); //需要左边数组k-rightLength个最大的数

}

}

if (right + 1 < end) {

int rightLength = end - right + 1;

if (rightLength > k) {

optQuickSort(arr, right+1, end, k);

}

}

}

}

============分割线============

min<=Vk<=max。

package com.xylx.utils.selectK;

import java.util.ArrayList;

import java.util.List;

/**

*/

public class BinSearchSelectK {

public static void main(String[] args) {

int[] arr = Constans.getLengthArr(100);

Constans.printArr(arr);

selectK(arr);

}

public static void selectK(int[] arr) {

List<Integer> result = getMaxMin(arr);

int max = result.get(0);

int min = result.get(1);

while (max - min > 1) {

int mid = (max + min)/2;

int total = getGTTotal(arr, mid);

if (total >= Constans.K) {

min = mid;

} else {

max = mid;

}

}

System.out.println("min="+min+"  max="+max);

printK(arr, min);

}

private static void printK(int[] arr, int min) {

int index = 0;

System.out.println("最大的K个数:");

for (int i=0; i<arr.length; i++) {

if (arr[i] > min) {

System.out.print(arr[i]+"    ");

index++;

}

}

for (int i=0; i<(Constans.K-index); i++) {

System.out.print(min+"    ");

}

}

/**

* 查找数组中大于等于mid值大的数的个数

* @param arr

* @param mid

*/

public static int getGTTotal(int[] arr, int mid) {

int total = 0;

for (int i=0; i<arr.length; i++) {

if (arr[i] >= mid) {

total++;

}

}

}

/**

* 寻找数组中最大值和最小值

* @param arr

* @return 0:最大　1:最小

*/

public static List<Integer> getMaxMin(int[] arr) {

List<Integer> result = new ArrayList<Integer>();

if (arr == null || arr.length < 1) {

return result;

}

int max = Integer.MIN_VALUE;

int min = Integer.MAX_VALUE;

for (int i=0; i<arr.length; i++) {

if (arr[i] > max) {

max = arr[i];

}

if (arr[i] < min) {

min = arr[i];

}

}

return result;

}

}

CDN知道为什么是你？

DNS域名解析

### zongjh

2017/09/20
0
0

2013/01/06
183
0

2017/11/16
0
0
Algo-Practice: 算法实践(JavaScript & Java)，排序，查找、树、两指针、动态规划等

qcer
2017/12/20
0
0

ACM的竞赛性强,因此自己应该和自己的实际应用联系起来.适合自己的才是好的,有的人不适合搞算法,喜欢系统架构,因此不要看到别人什么就眼红,发挥自己的长处,这才是重要的. 第一阶段：练经典常用...

long0404
2015/06/24
0
0

Java 如何实现线程间通信？

40分钟前
2
0

41分钟前
2
0

tianma3798
52分钟前
1
0
Rainbond V5.0 Beta公测公告

Rainbond支撑企业应用的开发、架构、交付和运维的全流程，通过“无侵入”架构无缝衔接各类企业应用，底层资源可以对接和管理IaaS、虚拟机和物理服务器 Rainbond V5.0即日起开启Beta版本公测,...

2
0
Word Pattern(leetcode290)

Given a pattern and a string str, find if str follows the same pattern. Here follow means a full match, such that there is a bijection between a letter in pattern and a non-empt......

woshixin

2
0