如何将空间复杂度降至O(1)

Question

我试图回答以下问题：给定一个整数数组，其中每个整数出现次数都是奇数，除了其中的3个数字。请找出这三个数字。

到目前为止，我想到了暴力方法：

 public static void main(String[] args) {
    // TODO Auto-generated method stub

    int number[] = { 1, 6, 4, 1, 4, 5, 8, 8, 4, 6, 8, 8, 9, 7, 9, 5, 9 };
    FindEvenOccurance findEven = new FindEvenOccurance();
    findEven.getEvenDuplicates(number);

  }

  // Brute force
  private void getEvenDuplicates(int[] number) {

    Map<Integer, Integer> map = new HashMap<Integer, Integer>();

    for (int i : number) {

      if (map.containsKey(i)) {
        // a XOR a XOR a ---- - -- - - odd times = a
        // a XOR a ---- -- -- --- - even times = 0
        int value = map.get(i) ^ i;
        map.put(i,value);
      } else {
        map.put(i, i);
      }
    }

    for (Entry<Integer, Integer> entry : map.entrySet()) {

      if (entry.getValue() == 0) {
        System.out.println(entry.getKey());
      }

    }
  }

它可以工作，但不够高效。

输出：

1
5
6
8

但是问题指定我们需要在O（N）时间复杂度和O（1）空间复杂度内完成。 我的解决方案的时间复杂度是O（N），但空间复杂度也是O（N）。 有人能建议我用O(1)空间复杂度更好的方法吗？

谢谢。

- Sarah

---

"except 3 of them", and your example has 4 of them !?! “除了其中三个”，而你的例子有四个！？ - user1196549

实际上，第一条语句与代码和输出相矛盾。因此，一些解决方案尝试找到三个未配对的整数，而其他解决方案则展示了如何找到除未配对之外的所有整数。请编辑您的问题并严格指明您想要什么！ - Edgar Rokjān

由于您必须再次迭代地图以检索结果，所以时间复杂度不会超过 O(N) 吗？不管怎样，您可以在原地对其进行排序。时间将增加到n * log（n）或其某种变体，但空间复杂度将减少为零！ - Ravindra HV

我真的希望问题不是关于数字（对于任何固定在N之前的基数）- 示例没有给出任何线索。 - greybeard

关于你可以做什么的度量：可扩展性讨论。 - greybeard

Answer 1

我花了一些时间来解决这个问题。看起来我找到了解决方案。无论如何，我相信社区会帮助我检查下面列出的想法。

首先，我声明当未成对的整数数量等于1或2时，我们可以解决这个问题。在1个未成对的整数的情况下，我们只需要找到所有数组元素的XOR，它将是答案。在2个未成对的整数的情况下，解决方案变得更加复杂。但是这已经在之前讨论过了。例如，您可以在这里找到它。

现在让我们尝试解决未成对的整数数量为3的问题。

在开始时，我们还要计算所有元素的XOR。让我们把它表示为X。

考虑X中的第 i 位。我假设它等于0。如果它等于1，则下一个过程实际上是相同的，我们只需将0更改为1，反之亦然。

因此，如果X中的第 i 位等于0，我们有两种可能的情况。一种情况是所有未配对的整数在第 i 位都有0。另一种情况是一个未配对的整数在第 i 位有0，而两个未配对的整数在第 i 位有1。这个声明基于简单的XOR操作属性。因此，我们有一个或三个未配对的整数，在第 i 位具有0。

现在让我们将所有元素分成两组。第一组是整数，在第i位上有0，第二组是在第i位上有1的整数。还有我们的第一组包含一个或三个带'0'的未配对整数在第i位。如何获得第一组中未匹配整数的特定数量？我们只需要计算第二组中所有元素的XOR。如果它等于零，则所有的未配对整数都在第一组中，并且我们需要检查另一个i。否则，只有一个未配对的整数在第一组中，其他两个在第二组中，我们可以使用本答案开头的方法分别解决这两个问题。

关键观察点在于存在一个i，使得一个未成对的整数的第i位与另外两个未成对整数的第i位不同。在这种情况下，未成对的整数在两个组中都存在。这是基于以下事实的：如果没有这样的i，则未成对的整数在所有位置上的位都相似，并且它们相等。但根据问题陈述，这是不可能的。

此解决方案可以在不使用任何额外内存的情况下实现。总复杂度是线性的，具体取决于数组元素中位数的数量。

- Edgar Rokjān

---

@Ilya 我觉得我们不能把这样的问题简单地看成是数学问题。在实践中，我们认为XOR操作的复杂度为*O(1)*，因为位数总数是有限的。我只想表明我们可以解决这个问题，而不需要任何额外的大型数组，这些数组的大小取决于位数... - Edgar Rokjān

是的，也许吧，她没有说。但我的第二个观点是，原帖的解决方案可能比答案中的“改进”方案更好。因此，如果您的解决方案有效，我会将它们评为1）您的解决方案2）原帖3）Lashane和SGM1。并且所有的O(1)都在位数固定的条件下。 - Ilya

我认为这个解决方案寻找的是出现次数为奇数的整数，而不是偶数。链接的答案找到的是非重复的数字，例如奇数。问题要求的是出现次数为偶数的整数。 - Ben Jackson

根据第i位进行分组会导致O(n log n)的时间复杂度。这很好，但不是OP梦寐以求的解决方案。 - Christopher Oezbek

@ChristopherOezbek 我认为 XOR 是一个常数时间操作。我怀疑如果 OP 的梦想解决方案在非常严格的限制下是否可能。我的主要目标是决定如何避免使用额外的内存并最小化总复杂度。 - Edgar Rokjān

Answer 2

很遗憾，如果我们使用严格的空间限制，即O(1)空间受输入数组中最大空间使用量的限制，就不可能以O(1)空间和O(n)复杂度实现这样的解决方案。在宽松的空间意义下，其中一个任意大的整数仍适合于O(1)，你可以将计数器编码到这个整数的位中。从所有位都设置为1开始。当您在输入数组中遇到数字n时，请切换第n位。在结束时，所有剩余的1位代表了遇到偶数次的3个数字。

- Christopher Oezbek

---

关于您的第一个评论，我认为在复杂度方面理解“O(1)空间”为“超过输入本身的O(1)空间”是标准的。否则，像L这样的复杂度类将毫无意义。关于您的第二个评论，在复杂度中以这种方式访问任意大的整数通常与标准RAM模型相矛盾，在该模型中，只能在单位时间内访问大小为log(n)的整数。 - mhum

@Edgar：是的，那将是简单的方式。 - Christopher Oezbek

@EdgarRokyan：很抱歉，但是没有解决这个问题的方案能够满足给定的O约束条件。如果问题反过来：除了三个整数外，所有整数都存在偶数次，那么我们可以得到更好的解决方案（仍然不是O（1）空间）。 - Christopher Oezbek

我觉得我没有仔细阅读你的解决方案。你明确提到了约束条件。因此，考虑具有大元素的数组是没有意义的，因为在这种情况下，附加的大整数无法适应O(1)空间。 - Edgar Rokjān

然而，由于 OP 没有仔细说明她想要什么，我们解决了不同的问题。如果我们尝试找到三个非配对整数，似乎我可以在不使用大整数或额外数组的情况下解决这个问题。 - Edgar Rokjān

Answer 3

有两种方法来看待你的问题。

第一种方法是将其作为一个具有无限整数集的数学问题，它似乎是不可解的。

第二种方法是将其作为一个具有有限整数集的计算问题，你已经解决了它（恭喜！）。为什么？因为存储空间受到MAX_INT的限制，而与N无关。

注：一种明显的空间优化是仅存储值一次，在偶数计数时擦除先前的值，这样可以节省一半的空间。

关于@Lashane和@SGM1提供的其他答案：它们也解决了“计算”问题，但在大多数实际场景中，它们比你的解决方案效率低。为什么？因为它们预分配了一个512MB的数组，而不是按照数组中不同值的数量进行比例分配。由于数组很可能使用远少于MAX_INT的不同值，即使你为每个值存储32位而不是1位，你也很可能使用远少于512MB的空间。而且，对于具有更多位数的整数，预分配的数组会呈指数级增长，而你的解决方案仅取决于数组中的实际值，因此不受系统位数（即最大int值）的影响。

另请参阅this和this，以获取更好（占用空间较少）的算法。

- Ilya

---

我们需要一种评估算法实际复杂度的方法，因此通常限制自己使用非无限整数来进行评估。我们定义最大可能的整数（MAXSIZE）。在这种情况下，整数<= MAXSIZE上的XOR运算被认为需要O(1)时间（或者在某些系统中需要O(log(MAXSIZE))时间）。同样，每个整数<= MAXSIZE被认为需要O(1)空间（或者可能需要O(MAXSIZE)空间）。按照这些假设来评估算法是标准做法。 - Ben Jackson

@BenJackson 没关系，我只是想说除了Edgar的提议外，所有的解决方案都在空间上使用了O(MAXSIZE)，而原始提议（具有讽刺意味的是）实际上可能使用更少的空间。需要注意的是，Edgar的解决方案是在我的第一个答案之后添加的。 - Ilya

Answer 4

例如，假设允许的数字大小为4位，这意味着允许的数字范围从0到2⁴-1，即一个常数16。对于每个可能的输入，我们在整个数组上运行并xor此数字的出现情况，如果xor的结果为零，则将当前值添加到总体结果中。该解决方案的时间复杂度为O(16N)，即O(N)，并且仅使用一个额外变量来计算当前数字的xor，其空间复杂度为O(1)。

我们可以将此方法扩展到原始问题中，但是它在运行时间复杂度方面将具有非常大的常数，与原始输入中允许的位数成比例。

我们可以通过运行所有元素并查找所有输入数据的最高有效位来增强此方法，假设它是第10位，那么我们的运行时间复杂度将变为O(2¹⁰N)，也是O(N)。

另一种增强方法可以在下面的图像中找到，但仍然具有如上所述的最坏情况复杂度。

最后，我相信这个问题存在另一个更好的解决方案，但我决定分享我的想法。

编辑：

这张图片中的算法可能不太清晰，以下是对该算法的一些解释。
首先，根据位来将元素分组，也就是把位作为过滤器，在每个阶段对分组后的元素进行异或操作，直到异或结果为零，然后检查该组中的每个元素，因为它肯定包含至少一个所需的输出。如果两个相邻的过滤器结果大小相同，我们将停止此过滤器。下面的示例将更加清晰。
输入：1、6、4、1、4、5、8、8、4、6、8、8、9、7、9、5、9
我们首先根据最低有效位将元素分组。
第 1 位为零：6、4、4、8、8、4、6、8、8
6 xor 4 xor 4 xor 8 xor 8 xor 4 xor 6 xor 8 xor 8 = 4
因此，我们将继续根据第 2 位分组。
第 1 位为零且第 2 位为零：4、4、4、8、8、8、8
4 xor 4 xor 4 xor 8 xor 8 xor 8 xor 8 xor 8 = 4。
因此，我们将继续根据第 3 位分组。
第 1 位为零且第 2 位为零且第 3 位为零：8、8、8、8
8 xor 8 xor 8 xor 8 = 0
因此，我们将遍历此过滤器下的每个元素，因为异或的结果为零，我们将把 8 添加到到目前为止的结果中。
第 1 位为零且第 2 位为零且第 3 位为一：4、4、4
4 xor 4 xor 4 = 4
第 1 位为零且第 2 位为零且第 3 位为一且第 4 位为零：4、4、4
4 xor 4 xor 4 = 4。
因此，我们将在此处停止，因为此过滤器包含与上一个过滤器相同的大小。
现在我们将回到第 1 位和第 2 位的过滤器。
第 1 位为零且第 2 位为一：6、6
6 xor 6 = 0。
因此，我们将遍历此过滤器下的每个元素，因为异或的结果为零，我们将把 6 添加到到目前为止的结果中。
现在我们将回到第 1 位的过滤器。
第 1 位为一：9、5、9、7、9、1、1
现在我们将按照之前相同的过程继续进行。
完整示例请参见上面的图片。

- Mahmoud Emam

---

如果我不用太大力眯眼，你正在做一个“自定义”的计数排序。 - greybeard

是的，这与计数排序类似，但我首先考虑的是根据位分配元素，可以参见答案中的 图片，这是我最初想到的。 - Mahmoud Emam

如果你有从0到15的数字，那么O(16*n)就是o(n^2)。仅仅看一下树形结构就可以清楚地知道时间复杂度不是o(n)。 - Christopher Oezbek

@ChristopherOezbek 允许的数字范围是从0到15，但没有说明不允许重复，因此您可以有1000个数字，但它们的值在0到15的范围内。 - Mahmoud Emam

Answer 5

您提出的问题概述和示例不匹配。您在问题中说您正在寻找3个整数，但是示例显示了4个。

我不确定在没有额外约束条件的情况下是否可能。在没有排序列表且具有完整整数集的情况下，最坏情况的大小复杂度似乎总是至少为O(N-6) => O(N)。

如果我们从排序数组开始，那么是的，很容易解决，但是这个约束条件没有被指定。自己对数组进行排序将会太耗费时间或空间。

- Nick Kuznia

Answer 6

我尝试用Lashane的提议略微不同的方式回答：

char negBits[268435456]; // 2 ^ 28 = 2 ^ 30（负整数个数）/ 8（char大小）
char posBits[268435456]; // 类似于正数
int number[] = {1, 6, 4, 1, 4, 5, 8, 8, 4, 6, 8, 8, 9, 7, 9, 5, 9};
for (int num: number){
   if (num < 0){
       num = -(num + 1);// 如果不加1，将排除Integer.MIN_VALUE
       negBits[ << 4] ^= ((num & 0xf) >> 1);
   }
   else {
      posBits[num << 4] ^= ((num & 0xf) >> 1);
      // 获取正确的字符进行操作
      // 翻转位以代表整数值
   }
}
// 现在最难的部分是找到所有翻转后的值：
for (int i = 0; i < Integer.MAX_VALUE; i++){
    if (negBits[i << 4] & ((i & 0xf) >> 1)){
        System.out.print(" " + (-i - 1));
    }
    if (posBits[i << 4] & ((i & 0xf) >> 1)){
        System.out.print(" " + i);
    }
}

根据评论讨论，以下要点值得注意：

• 假设Java是32位。
• Java数组具有整数最大值的固有限制。

- SGM1

---

我对Lashane的答案和这里的相同反对意见。这个for循环for(int num: number)必须包含一个计数器，该计数器通过数组的N个不同索引进行计数，并将值分配给num。即使您认为int是恒定大小，该计数器的大小至少必须为logN位，否则该循环是不可能的。如果少于N个状态可用内存来表示，则无法跟踪下一个数字，或在正确时间退出循环。 - Chris Beck

你认为你的解决方案使用了额外的 O(1) 内存吗？ - Edgar Rokjān

“Assumes 32 bit”这个前提条件改变了问题（很多）。 - Ilya

@Ilya 我同意，但这是我得到的最好的结果，滥用它仍然绑定在最小整数和最大整数之间的事实。 - SGM1

没有“Java”标签，这是仅限于Java吗？ - Ilya