问题:
给定一个包含n个对象的数组,其键只有四个值之一。重新排列数组,使相同类型的对象出现在一起。使用O(1)额外空间和O(n)时间。
我无法想象超过三组(荷兰国旗问题)。非常感谢您提供帮助。
例如a[6]={1,2,3,4,3,1}; 那么结果应该是{1,1,2,3,3,4}或任何顺序,只有数字分组的顺序很重要(即,结果不必按升序排列)
给定一个包含n个对象的数组,其键只有四个值之一。重新排列数组,使相同类型的对象出现在一起。使用O(1)额外空间和O(n)时间。
我无法想象超过三组(荷兰国旗问题)。非常感谢您提供帮助。
例如a[6]={1,2,3,4,3,1}; 那么结果应该是{1,1,2,3,3,4}或任何顺序,只有数字分组的顺序很重要(即,结果不必按升序排列)
#include <iostream>
using namespace std;
int main() {
int a[] = {1,2,3,4,3,1,2,3,3,4};
int size = sizeof(a) / sizeof(int);
int ptr = 0;
for(int flag=1;flag <= 4;++flag){
for(int i=ptr;i<size;++i){
if(a[i] == flag){
swap(a[i],a[ptr++]);
}
}
}
for(int i=0;i<size;++i){
cout<<a[i]<<" ";
}
}
更新:
对于 独立于组数
,您可以使用 trie 数据结构。Trie 由每个数字的二进制表示组成,最后一个节点保存那个组元素出现次数的计数值。
由于我们可以用32位表示整数,因此Trie占用的空间将更少,并且不会随着组数的增加而增长。
因此,空间复杂度为O(1)。时间复杂度为O(n + log(max_number)* n)。
def partition(nums):
key1_index = 0
key2_index = 0
key3_index = 0
key4_index = len(nums) - 1
while key3_index <= key4_index:
if nums[key3_index] == 1:
nums[key1_index], nums[key3_index] = nums[key3_index], nums[key1_index]
key1_index += 1
if key2_index < key1_index:
key2_index += 1
if nums[key3_index] != 2:
key3_index += 1
elif nums[key3_index] == 2:
nums[key3_index], nums[key2_index] = nums[key2_index], nums[key3_index]
key2_index += 1
key3_index += 1
elif nums[key3_index] == 3:
key3_index += 1
else:
nums[key3_index], nums[key4_index] = nums[key4_index], nums[key3_index]
key4_index -= 1
return nums
这是一个单遍 O(n)
解决方案,使用 O(1)
空间。基本思路类似于必须排序三个键的情况。第一个键是通常三个键情况下的额外复杂度。我们保留 4 个指针,每个键一个。当我们遇到一个值等于 key1
的索引时,我们将其与下一个位置交换,这个位置应该插入 key1
。然后,我们递增 key1_index
。现在,当我们递增 key1_index
时,这意味着我们还需要递增 key2_index
,但并不总是如此。何时需要在递增 key1_index
后递增 key2_index
?当 key2_index
落后于 key1_index
时。例如:
初始数组:[3, 1, 1, 2]
# key1_index = 0
和 key2_index = 0
当遇到nums[1] = 1
时,我们知道它需要放在key1_index = 0
处。因此,我们将其放在那里,key1_index
变为1
。但现在,key2_index
落后了。所以,我们也需要增加它。否则,当我们遇到nums[3] = 2
时,它将覆盖我们刚刚放置的第一个1
。
什么情况下不需要增加key2_index
?当key2_index
已经被增加并且具有比key1_index
更大的值时。在这种情况下,即使我们遇到key1
,它也不会影响key2
的下一个插入位置。
key3
,但不总是这样。当交换key1_index
和key3_index
时,我们可能会将在key1_index
中的key2
带到key3_index
位置。例如:[1, 1, 2, 2, 3, 3, 1]
^ ^
| |
| This is where we're currently at, encountering 1.
|
This is the position where next 1 (key1) will be inserted
[1, 1, 1, 2, 3, 3, 2]
^ ^ ^
| | |
| Next 2 will be inserted here
| |
| |
| We've brought 2 here which need to be put back to their proper
| place (So we can't increment key3. Otherwise, 2 will remain here.)
|
|
1 (key1) has been put into its place
key3_index
与key1_index
交换,使得在key3_index
处出现除了key2
之外的任何东西,则我们不需要做任何事情。因为排序顺序将保持不变。为什么?请记住,key4
应从数组的后面插入。如果交换将一个key3
带到key3_index
,这意味着在key1
和key3
之间没有key2
。所以,我们不需要做任何事情。O(n)的DNF解决方案从最低和最高索引开始形成两个集合,并知道在它们之间形成第三个集合是同质的,因此不需要进一步处理。
如果将集合数量增加到四个或更多,则仍然可以以相同的“精神”形成顶部和底部集合,因此在O(n)时间内完成,但中间部分仍然是混合的,必须再次进行检查。这就是为什么它不再是“纯”的O(n) - 数组/序列只有两个端点。
int a[] = { 1,2,3,4,3,1,2,3,3,4 };
int size = sizeof(a) / sizeof(int);
int bottom = 0, top = size - 1;
for (int bottomband = 1, topband = 4; topband > bottomband; bottomband++, topband--) {
int i = bottom;
while (i <= top) {
if (a[i] == bottomband) {
swap(a[i], a[bottom]);
i++;
bottom++;
}
else if (a[i] == topband) {
swap(a[i], a[top]);
top--;
}
else
i++;
}
}
for (int i = 0; i<size; ++i) {
cout << a[i] << " ";
}
你可以在里面识别到“经典”的DNF循环(当topband
从3开始时,它就变成了原始算法)。a[]
是从另一个解决方案中取出的,以便进行比较。
swap
调用的次数显示有10次,这也适用于Vivek的解决方案。这部分是巧合,部分是因为两个解决方案都愉快地交换相同的元素,因为只有“当前”元素被检查,而另一个元素(位于bottom
、top
或ptr
)则不会被检查。例如,两个算法的第一件事情都是将列表开头的1
与其自身交换。
通过跳过连续的相同元素块(在改变带和调整标记时都必须这样做),代码变得越来越长...
int bottom = 0, top = size - 1;
for (int bottomband = 1, topband = 4; topband > bottomband; bottomband++, topband--) {
while (a[bottom] == bottomband)bottom++;
while (a[top] == topband)top--;
int i = bottom;
while (i <= top) {
if (a[i] == bottomband) {
swap(a[i], a[bottom]);
i++;
bottom++; // it would be done by the next line in fact
while (a[bottom] == bottomband)bottom++;
}
else if (a[i] == topband) {
swap(a[i], a[top]);
top--; // this one too
while (a[top] == topband)top--;
}
else
i++;
}
}
...并且对swap
的调用次数减少到6。虽然复杂度类别没有改变(我认为),但是对于一个可能代价高昂的操作的实际调用次数已经减少了40%。这就是理论和实践之间的差异。
让unik_elems数组包含不同的元素,其中它们之间可以进行比较。即我们可以使用<
或>
。例如[1,2,3,4]。
因此,如果这些是4个不同的元素,则我们可以选择第一个枢轴为2,并将1组合并到2的左侧,然后我们将枢轴更改为3并将2组合并到3的左侧,因为我们已经分组了0,所以我们将从未分组的数组开始的索引。这样,我们就可以将枢轴更改为4。假设我们首先对给定的4个不同元素进行排序。
nums = [1,4,3,2,2,3,4,1,3,2,4,1,3,2,4,1]
unclassified = 0
unik_elems = [1,2,3,4]
for pivot_idx in range(1, len(unik_elems)):
pivot = unik_elems[pivot_idx]
# we start the array from the index from where the elements are unclassified.
# Hence, when selecting 3 as pivot in this example, the elements on the left
# of unclassified will be 1 and hence wont we touched when we use 3 as the pivot.
for idx in range(unclassified, len(nums)):
if nums[idx] < pivot:
nums[idx], nums[unclassified] = nums[unclassified], nums[idx]
unclassified += 1
时间复杂度 = O(N),由于有4个不同的元素,因此它将是3次遍历的解决方案。