对于一个无序数组，数组中元素为互不相同的整数，请返回其中最小的k个数，顺序与原数组中元素顺序一致。
给定一个整数数组A及它的大小n，同时给定k，请返回其中最小的k个数。
测试样例：
[1,2,4,3],4,2
返回：[1,2]
[编程题]无序数组中最小的k个数
汗颜！哥们想到的分治算***改变数组输出顺序，只能暴力拆解，用一个数组接收A，直接排序，得到第k小的元素。
import java.util.*;
public class KthNumbers {
public int[] findKthNumbers(int[] A, int n, int k) {
// write code here
int[] arr = new int[k];
int m = GetK(A,k);
for(int i=0,j=0;i<n&&j<k;i++){
if(A[i]<=m){
arr[j] = A[i];
j++;
}
}
return arr;
}
public static int GetK(int[] A,int k){
int[] tmp = new int[A.length];
for(int i=0;i<A.length;i++){
tmp[i] = A[i];
}
Arrays.sort(tmp);
return tmp[k-1];
}
}
发表于 2019-04-16 23:10:47
回复(0)
public class KthNumbers {
public static int[] findKthNumbers(int[] A, int n, int k) {
int count = n - k;
int length = A.length;
while (count > 0) {
int maxNumberIndex = 0;
int i;
for (i = 1; i < length; i++) {
if (A[maxNumberIndex] < A[i]) {
maxNumberIndex = i;
}
}
for (int j = maxNumberIndex; j < length - 1; j++) {
A[j] = A[j + 1];
}
length--;
count--;
}
int[] result = new int[length];
for (int i = 0; i < length; i++) {
result[i] = A[i];
}
return result;
}
}
发表于 2018-09-26 17:45:16
回复(0)
import java.util.*;
//两次排序，先按大小选出前k个小的数，再按其下标的大小排序
public class KthNumbers {
public int[] findKthNumbers(int[] A, int n, int k) {
// write code here
List<V> list=new ArrayList<V>();
for(int i=0;i<n;i++){
list.add(new V(A[i],i)); //新建一个类，包含大小和下标
}
Collections.sort(list,new Comparator<V>(){ //按大小排序
@Override
public int compare(V o1,V o2){
Integer val1=o1.val;
Integer val2=o2.val;
if(val1!=val2){
return val1.compareTo(val2);
}
else{
Integer idx1=o1.idx;
Integer idx2=o2.idx;
return idx1.compareTo(idx2);
}
}
});
list=list.subList(0,k);//截取前k小的数
Collections.sort(list,new Comparator<V>(){ //按下标排序
@Override
public int compare(V o1,V o2){
Integer idx1=o1.idx;
Integer idx2=o2.idx;
return idx1.compareTo(idx2);
}
});
int[] res=new int[k];
for(int i=0;i<k;i++){
res[i]=list.get(i).val;
}
return res;
}
public class V{
int val;
int idx;
public V(int val,int idx){
this.val=val;
this.idx=idx;
}
}
}
//两次排序，先按大小选出前k个小的数，再按其下标的大小排序
public class KthNumbers {
public int[] findKthNumbers(int[] A, int n, int k) {
// write code here
List<V> list=new ArrayList<V>();
for(int i=0;i<n;i++){
list.add(new V(A[i],i)); //新建一个类，包含大小和下标
}
Collections.sort(list,new Comparator<V>(){ //按大小排序
@Override
public int compare(V o1,V o2){
Integer val1=o1.val;
Integer val2=o2.val;
if(val1!=val2){
return val1.compareTo(val2);
}
else{
Integer idx1=o1.idx;
Integer idx2=o2.idx;
return idx1.compareTo(idx2);
}
}
});
list=list.subList(0,k);//截取前k小的数
Collections.sort(list,new Comparator<V>(){ //按下标排序
@Override
public int compare(V o1,V o2){
Integer idx1=o1.idx;
Integer idx2=o2.idx;
return idx1.compareTo(idx2);
}
});
int[] res=new int[k];
for(int i=0;i<k;i++){
res[i]=list.get(i).val;
}
return res;
}
public class V{
int val;
int idx;
public V(int val,int idx){
this.val=val;
this.idx=idx;
}
}
}
编辑于 2018-05-28 16:50:04
回复(0)
- 复制一个原数组命名为CA
- 将CA升序排序，找到临界值CA[k-1]
- 遍历原数组A，将小于等于CA[k-1]的数放到一个新数组中，over.
public static int[] findKthNumbers(int[] A, int n, int k) { int[] CA = new int[n]; System.arraycopy(A, 0, CA, 0, n); Arrays.sort(CA); int[] min = new int[k]; int index = 0; int number = CA[k - 1]; for (int i = 0; i < n; i++) { if (A[i] <= number) { min[index] = A[i]; index++; } } return min; }
发表于 2017-11-04 09:55:27
回复(0)
首先对数列进行排序， 获取到第k小的数字， 然后， 遍历原序列， 凡是<=k的都加到结果数列中。
import java.util.*;
public class KthNumbers {
public int[] findKthNumbers(int[] A, int n, int k) {
int B[] = new int[A.length];
for (int i = 0; i < A.length; i++) {
B[i] = A[i];
}
java.util.Arrays.sort(A);
int kth = A[k-1];
int[] result = new int[k];
int index = 0;
for(int i=0; i< B.length; i++){
if( B[i] <= kth){
result[index] = B[i];
index++;
}
}
return result;
}
}
发表于 2017-08-27 20:03:03
回复(0)
对于本题应首先明确一点：需要保留k个较小的元素，那也就意味着可以删除除n-k个较大的元素。
具体实现代码如下：
public class KthNumbers {
public static int[] findKthNumbers(int[] A, int n, int k) {
// write code here
int count=n-k;//要删除的元素数量
int LENGTH=A.length;//实际数组中的元素个数
while(count>0){
//删除当前数组中最大的元素
int max_index=0;//记录最大元素的下标
int i;
for(i=1;i<LENGTH;i++){//寻找最大元素并记录其在数组中的下标
if(A[max_index]<A[i]){
max_index=i;
}
}
//删除当前最大元素即max_index
for(int j=max_index;j<LENGTH-1;j++){
A[j]=A[j+1];
}
LENGTH--;//注意删除后数组的个数要减一
count--;
}//end while****************
int res[] = new int[LENGTH];//结果集数组
for(int i=0;i<LENGTH;i++){//当删除完元素后只需将保留下的k个元素赋值到结果数组中
res[i]=A[i];
}
return res;
}
}
发表于 2017-04-20 22:00:05
回复(0)
import java.util.*;
public class KthNumbers {
public int[] findKthNumbers(int[] A, int n, int k) {
// write code here
int B [] =new int[A.length];
int result []=null;
ArrayList resultList = new ArrayList();
for(int i=0;i<A.length;i++){
B[i]=A[i];
}
QuickSort.quickSort(B);
int miniK=B[k-1];
for(int i=0;i<A.length;i++){
if(A[i]<=miniK){
resultList.add(A[i]);
}
}
result=new int[resultList.size()];
for(int i=0;i<resultList.size();i++){
result[i]=(int) resultList.get(i);
}
return result;
}
public static class ArrayUtils {
public static void printArray(int[] array) {
System.out.print("{");
for (int i = 0; i < array.length; i++) {
System.out.print(array[i]);
if (i < array.length - 1) {
System.out.print(", ");
}
}
System.out.println("}");
}
public static void exchangeElements(int[] array, int index1,
int index2) {
int temp = array[index1];
array[index1] = array[index2];
array[index2] = temp;
}
}
public static class QuickSort {
public static void main(String[] args) {
int[] array = { 9, 8, 7, 6, 5, 4, 3, 2, 1, 0, -1, -2, -3
};
System.out.println("Before sort:");
ArrayUtils.printArray(array);
quickSort(array);
System.out.println("After sort:");
ArrayUtils.printArray(array);
}
public static void quickSort(int[] array) {
subQuickSort(array, 0, array.length - 1);
}
private static void subQuickSort(int[] array, int start, int
end) {
if (array == null || (end - start + 1) < 2) {
return;
}
int part = partition(array, start, end);
if (part == start) {
subQuickSort(array, part + 1, end);
} else if (part == end) {
subQuickSort(array, start, part - 1);
} else {
subQuickSort(array, start, part - 1);
subQuickSort(array, part + 1, end);
}
}
private static int partition(int[] array, int start, int end)
{
int value = array[end];
int index = start - 1;
for (int i = start; i < end; i++) {
if (array[i] < value) {
index++;
if (index != i) {
ArrayUtils.exchangeElements(array, index, i);
}
}
}
if ((index + 1) != end) {
ArrayUtils.exchangeElements(array, index + 1, end);
}
return index + 1;
}
}
}
发表于 2016-06-24 19:12:40
回复(1)
动态规划的思想，从n个中找出k个，所以就代表了你小于的数量一定要大于等于n-k次。
举个例子{1，2，3，4} 4，1 那么你这个数最起码要比三个数字小才可以算答案里面。
而且答案是不能排序，所以就要建新数组来实现了。
import java.util.*;
public class KthNumbers {
public int[] findKthNumbers(int[] A, int n, int k) {
// write code here
int[] res = new int[k];
int idx = 0;
for(int i = 0; i < n; i++) {
int tmp = 0;
for(int j = 0; j < n; j++) {
if(A[i] < A[j]) {
tmp++;
}
}
if(tmp >= n - k) {
res[idx++] = A[i];
}
}
return res;
}
}
发表于 2016-06-18 11:35:54
回复(2)
问题信息
通过挑战的用户
查看代码-
2022-11-08 22:49:28
-
2022-09-06 19:36:46 -
2022-08-30 08:39:37
-
2022-08-29 08:47:34 -
2022-08-26 10:40:35
相关试题
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K1座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
