O(N)的时间寻找最大的K个数
public class Test {
public static int partition(int[] array
, int left
, int right
) {
int cur
= array
[left
];
while (left
< right
) {
while (right
> -1 && array
[right
] <= cur
) --right
;
array
[left
] = array
[right
];
while (left
< array
.length
&& array
[left
] >= cur
) ++left
;
array
[right
] = array
[left
];
}
array
[left
] = cur
;
return left
;
}
public static int[] maxK(int[] array
, int k
) {
if (null
== array
|| k
< 1) {
return null
;
}
int len
= array
.length
;
if (k
>= len
) {
return array
;
}
int left
= 0;
int right
= len
- 1;
while (left
< right
) {
int partition
= partition(array
, left
, right
);
if (partition
+ 1 == k
) {
right
= partition
;
break;
}
if (partition
+ 1 < k
) {
left
= partition
;
} else {
right
= partition
;
}
}
int[] res
= new int[k
];
for (int i
= 0; i
< k
; ++i
) {
res
[i
] = array
[i
];
}
return res
;
}
public static void main(String
[] args
) {
int[] array
= {3, 4, 6, 1, 2, 7, 3, 5, 6};
int[] res
= maxK(array
, 4);
for (int val
: res
) {
System
.out
.print(val
+ " ");
}
}
}
由于寻找partition + 1 == k就行，最多只需n次，所以时间复杂度是O(n)
