-1

我有一个数组 int[] a= {5,3,1,2} 并且我想创建一个方法来挑选“k”个最小数字并返回一个按升序排列的具有 k 个最小整数的数组。但是当我运行这段代码时，我得到了输出：[1,3]。我知道代码以某种方式跳过了一些数字，但我无法扭曲我的大脑来修复它。有任何想法吗？

编辑：不对原始数组进行排序。

 public static int[] nrSmallest(int[] a, int k)  {
            if(k <1 || k>a.length)
                throw new IllegalArgumentException("must be at least 1");
            int[] values= Arrays.copyOf(a, k);
            Arrays.sort(values);
            int counter= 0;  
                for(int i= k; i < a.length; i++)    {
                        if(a[i]< values[counter])   {
                            for(int j= k-1; j> counter; j--)    {
                                values[j]= values[j-1];
                            }
                                values[counter]= a[i];  
                        }
                        if(counter< k) counter++;
                }
            return values;
        }

编辑：Joop Eggen 为我解决了这个问题。向下滚动以查看答案。谢谢！

4

6 回答 6

4

正如评论中已经指出的那样，只需返回排序数组的一部分。

public static int[] nrSmallest(int[] a, int k)  {
    // check parameters..

    // copy all so we don't sort a
    int[] sorted = Arrays.copyOf(a, a.length);
    Arrays.sort(sorted);
    return Arrays.copyOf(sorted, Math.min(k, sorted.length));
}
于 2013-09-17T16:16:36.413 回答
3

如果您无法修改原始数组，这通常使用某种类型的优先级队列来完成，通常是二进制堆。

您在示例中使用的方法是 O(n^2)，并使用 O(k) 额外空间。对原始数组进行排序并选择前 k 个项目是 O(n log n)。如果复制数组然后对其进行排序，它会使用 O(n) 额外空间。

使用堆是 O(n log k)，并且需要 O(k) 额外空间。

有一个 O(n) 解决方案涉及操作原始数组（或制作数组的副本并对其进行操作）。请参阅快速选择。

我自己的测试表明，Quickselect 在一般情况下更快，但是当要选择的项目数（k）小于总项目数（n）的 1% 时，堆选择更快。请参阅我的博客文章，当理论遇到实践时。当从 200 万个列表中选择前 100 个项目时，这非常方便。

于 2013-09-17T17:09:08.343 回答
1

（更正）要保留您的代码：

            for (int i= k; i < a.length; i++) {
                    if (a[i] < values[counter]) { // Found small value
                        // Insert sorted
                        for (int j = k-1; j >= 0; j--) {
                            if (j == 0 || a[i] > values[j-1]) { // Insert pos
                                // Move greater ones up.
                                for (int m = k - 1; m > j; m--) {
                                    values[m] = values[m - 1];
                                }
                                values[j] = a[i]; // Store
                                break; // Done
                            }
                        }
                    }
            }
于 2013-09-17T16:23:10.990 回答
0

int[] values= Arrays.copyOf(a, k); 这条线是错误的。您只复制 k 个元素。但是您应该复制所有元素，然后对数组进行排序。

于 2013-09-17T16:17:27.057 回答
0

您可以使用快速排序的“枢轴”思想，枢轴表示该数字在数组中的“排名”，因此您的最终目标是在索引“k”处有一个枢轴，这将导致子数组小于第 K元素，换句话说，前 K 个最小的数字（未完全排序）。

于 2013-09-17T18:15:12.513 回答
0

首先对数组进行排序，然后将排序后的数组部分返回到 k。

public static int[] nrSmallest(int[] a, int k)  {
        if(k <1 || k>a.length)
            throw new IllegalArgumentException("must be at least 1");
        Arrays.sort(a);        
        return Arrays.copyOf(a,k);
    }
于 2013-09-17T16:30:12.130 回答