我在 Atrenta 的面试中被问到一个有趣的问题。这是对复杂度为 O(n) 的数组进行排序,我说这是不可能的,但他坚持认为这是不可能的,即使在采访之后也是如此。
就像这样。
你有一个数组,可以说:[1,0,1,0,1,1,0] 这需要排序。必须在数组中完成的事情(在某种意义上不涉及其他数据结构。
我没有,我认为不可能做任何复杂度为 O(n) 的事情。我能想到的最好的是 O(n * log n),我的知识来自维基百科。
如果您知道,请给我您的想法和方法。
在您的示例中,数组中只有两个不同的值,因此您可以使用计数排序:
zero_count = 0
for value in array:
if value == 0:
zero_count += 1
for i in 0 ... zero_count:
array[i] = 0
for i in zero_count ... array.size:
array[i] = 1
基数排序是一系列更普遍适用的 O(n) 排序。
它是比较排序,平均需要 Omega(n * log n) 比较,因此不能在最坏情况或平均情况线性时间运行。
从两端遍历数组,并在需要时交换 1 和 0。在 O(n) 中运行,但具有所有 if 条件(类似方法的蛮力。可能不是预期的答案);)
int i = 0 ;
int j = array.size -1 ;
for ( i = 0 ; i < j ; ) {
if( array[i] == 1) {
if( array[j] == 0 ) {
array[j] = 1 ; array[i] = 0 ; //Swap
i++; j--;
continue;
}
//else
j--;
continue;
}
//else
if( array[j] == 0 ) {
i++;
continue;
}
//else
i++ ;
j--;
}