zongjh 发表于10个月前

• 发表于 10个月前
• 阅读 13
• 收藏 0
• 评论 0

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

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域名解析

×