2

我正在尝试完成一个 smoosh() 方法，它需要一个整数数组。完成后，数组仍应包含相同的数字，但只要数组有两个或多个连续的重复数字，它们就会被该数字的一个副本替换。因此，在 smoosh() 完成后，数组中没有两个连续的数字是相同的。

数组末尾的任何未使用元素都设置为 -1。

例如，如果输入数组是

[ 1 1 0 0 4 4 5 0 0 0 7 ]

它读到

[ 1 0 4 5 0 7 ]

smoosh() 完成后。

方法签名是： public static void smoosh(int[] ints)

我能够这样做：

for (int i=0; i<ints.length-1; i++) {
    if (ints[i+1]==ints[i])
        ints[i]=-1;
}
for (int i=0; i<ints.length-1; i++) {
    if (ints[i]==-1) {
        for (int j=i+1; j<ints.length; j++) {
            if (ints[j]!=-1) {
                //swap ints[j] and ints[i] and then break;
            }
        }
    }
}

但是，这将是 O(n2) 时间（尽管几乎就位）。

我觉得应该有一些 O(n) 就地方法来做到这一点，但我不知道怎么做。谁能想到任何 O(n) 就地算法？（显然，如果您制作另一个相同大小的数组来帮助处理，那么您可以轻松获得 O(n) ，但这不是我想要的，因为那还没有到位......）

谢谢！

4

3 回答 3

4

基本上如下。这个 O(n) 时间、O(1) 空间的“算法”实际上是 Python 代码，因为这是一种非常适合教授基本算法的语言，只要你避免使用所有复杂的东西，比如 lambda。

我现在实际上正在用它来教我 8 岁的儿子，因为他对我整天在工作中所做的事情表示了兴趣。

array = [1, 1, 0, 0, 4, 4, 5, 0, 0, 0, 7]

print array

count = len (array)
last = array[0] - 1
toidx = 0
for fromidx in range (0, count):
    if array[fromidx] != last:
        array[toidx] = array[fromidx]
        toidx = toidx + 1
        last = array[fromidx]
while toidx < count:
    array[toidx] = -1
    toidx = toidx + 1

print array

这个的输出是：

[1, 1, 0, 0, 4, 4, 5, 0, 0, 0, 7]
[1, 0, 4, 5, 0, 7, -1, -1, -1, -1, -1]

正如您的规格要求的那样。

它基本上通过数组运行两个索引，fromix无论如何索引都会前进一个。仅当 at 的值与最后传输的值不同时，toidx索引才会前进。fromidx最后传输的初始值设置为与第一个元素不同的值，以确保传输第一个元素。

换句话说，在该条件为真的每次迭代中，from索引处的值被复制到toidx索引中，toidx索引增加，并且last值被更新。如果 at 的值fromidx与上次传输的值相同，toidx则不更新索引。

然后，最后，所有剩余的值都设置为 -1。

由于您的规范要求用​​ -1 填充数组的其余部分，这就是我在上面的代码中所做的。

但是，您的示例结果不包含负值，因此，如果您需要截断数组而不是填充数组-1，则基本上将while末尾的循环替换为数组截断，使其大小现在为toidx。

在 Python 中，您可以通过以下方式执行此操作：

array = array[0:toidx]
于 2012-10-01T03:54:10.230 回答
3

不需要你的内循环。您只需要跟踪您访问的最后一个值是什么，然后开始跳过，直到找到一个“新”数字。例如在伪代码中

previous = null;
newarray = array();
newpos = 0;
for (i = 0; i < oldarray.length; i++) {
   if (oldarray[i] == previous) {
      continue; // got a duplicate value, so skip it.
   } else {
      newarray[newpos++] = oldarray[i];
      previous = oldarray[i];
   }
}
for (i = newpos; i < oldarray.length; i++) {
   newarray[i] = -1; // fill in any empty slots
}

现在你只剩下 O(n) 了。

于 2012-10-01T03:54:48.277 回答
1

如果您使用 aLinkedList代替，您可以使用 a ListIteratorfor 循环，将前一个值的值存储在列表中，ListIterator.remove如果它等于当前值则调用。

于 2012-10-01T03:56:25.420 回答