排序算法,不允许计算元素

Question

我在公司面试中看到了这个问题,但我不清楚这个问题.你能否澄清我的怀疑？

问题:编写一个程序来对整数数组进行排序,该数组只包含0,1和2.对不允许的元素进行计数,您需要在O(n)时间复杂度下进行计数.

Ex数组:{2,0,1,2,1,2,1,0,2,0}

Answer 1

输出到链表.

• 记住列表的开头.
• 记住1开始的位置.
• 记住列表的结尾.

贯穿整个阵列.

• 如果遇到0,请将其添加到链接列表的第一个位置.
• 如果遇到1,请在1的位置后添加.
• 如果遇到2,请在列表末尾添加.

HTH

乐

Answer 2

由于数组中的值很少，因此只需计算每种类型的数量，然后使用它来重新填充数组。我们还利用了这些值从 0 开始连续的事实 - 使其与典型的 java int 循环相匹配。

整个排序算法只需要三行代码：

public static void main(String[] args)
{
    int[] array = { 2, 0, 1, 2, 1, 2, 1, 0, 2, 0 };

    // Line 1: Define some space to hold the totals
    int[] counts = new int[3]; // To store the (3) different totals

    // Line 2: Get the total of each type
    for (int i : array) counts[i]++;

    // Line 3: Write the appropriate number of each type consecutively back into the array:
    for (int i = 0, start = 0; i < counts.length; start += counts[i++]) Arrays.fill(array, start, start + counts[i], i);

    System.out.println(Arrays.toString(array));
}

输出：

[0, 0, 0, 1, 1, 1, 2, 2, 2, 2]

我们在任何时候都没有提到array.length，也不关心数组有多长。它对数组进行迭代，仅接触每个元素一次，从而使该算法达到所需的 O(n) 。