返回k个最小元素的java数组
从数组int[] a
中,我想找到并返回一个k.length的数组,其中包含排序的k个最小元素
数组a的内容不能有任何更改。在创建一个k.length的帮助数组后,我从a复制k个first值,然后对其排序
在此之后,如果数组a中有任何元素小于帮助数组中的元素,我将其放置在正确的位置,最后一个元素消失,依此类推
方法:
public static int[] kMinst(int[] a, int k)
可能的投入:
int[] a = {1,2,3,4,5,6,7,8,9,10}
kMinst(a, a.length);
输出:
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
另一项输入:
int[] b = {4,3,2,1}
kMinst(b, 3);
输出:
[1, 2, 3]
到目前为止我所拥有的。它不起作用,效率太低:
public static int[] kMinst(int[] a, int k) {
if (k < 1 || k > a.length) {
throw new IllegalArgumentException("k har ikke riktig verdi!");
}
int[] verdier = new int[k];
for (int i = 0; i < verdier.length; i++) {
verdier[i] = a[i];
}
sortering(verdier);
for (int i = verdier.length; i < a.length; i++) {
for (int j = verdier.length - 1; j > 0; j --) {
if (a[i] < a[j]) {
int temp = a[j];
for (int l = verdier.length - 1; l > j; l--) {
a[l] = a[l - 1];
}
a[j] = temp;
}
}
}
return verdier;
}
# 1 楼答案
我会使用一个
Set
来丢弃重复项,并使其成为一个TreeSet
,因此它自己进行所有排序# 2 楼答案
我想下面的代码符合你的目的
公共类SortArray{
# 3 楼答案
下面是一个在包含唯一元素的数组中查找K个最小元素的实现。如果希望允许重复,可以使用java。util。设置以消除重复项。 它基于随机快速选择算法,最坏情况的顺序为n。它输出原始数组中K个最小元素的无序序列
首先,它找到第k个最小元素的索引,并对列表[k]进行部分无序排序。因此,最终结果将包含K个数字,这些数字在数组中较小,第K个最小元素位于最右边的位置
# 4 楼答案
我会用英语写,但如果你想用挪威语解释,我也可以。我不会为您编写任何代码存根,因为这是一个家庭作业,但请尝试想象您首先需要完成什么: 我猜数组a是未排序的,或者至少是按文本中显示的相反方式排序的? 一个不能改变的目标。 k、 长度为k时,应包含a中最小值数的k个数量。 k必须排序
首先也是最重要的,你如何解决问题1?我会做什么(一开始效率更低,但您不必编写那么多代码): 检查数组a,首先将索引0中的第一个整数保存到k中。让i++发挥它的魔力,然后调用一个方法,在其中发送整个数组k和新整数。让它检查(使用compareTo()-method)新的int是否低于k中每个索引中的整数,将其他数字一直向前移动一个索引(记住要检查null值,或者lse:NPE)。返回此新数组。 这将允许您保存k个最低的数字,对它们进行排序,而不更改a。我认为这将解决您的整个问题
# 5 楼答案
您可以对数组进行排序,并从中获取前k个元素
希望有帮助:)
# 6 楼答案
您可以从原始数据构建一个堆,该堆将是O(nlogn),然后从该堆中获取k个元素,在最坏的情况下,该堆也将是O(nlogn)