首页
学习
活动
专区
工具
TVP
发布
社区首页 >问答首页 >如何使空间复杂度为O(1)

如何使空间复杂度为O(1)
EN

Stack Overflow用户
提问于 2016-01-16 03:56:28
回答 2查看 2.1K关注 0票数 17

我试图回答下面的问题:你有一个整数数组,使得每个整数出现奇数次,除了其中的3个。找到这三个数字。

到目前为止,我使用的是蛮力方法:

代码语言:javascript
复制
 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());
      }

    }
  }

它工作得很好,但效率不高。

o/p:

代码语言:javascript
复制
1
5
6
8

但问题指出,我们需要在O(1)空间和O(N)时间复杂度内完成这项工作。对于我的解决方案,时间复杂度是O(N),但空间复杂度也是O(N)。有人能建议我用O(1)空间做这件事的更好的方法吗?

谢谢。

EN

回答 2

Stack Overflow用户

发布于 2016-01-27 04:23:08

不幸的是,如果我们使用严格的空间感,即O(1)空间被输入阵列中使用的最大空间所约束,则不可能获得O(1)空间和O(n)复杂度的解。

在弱空间意义下,一个任意的大整数仍然适合O(1),您可以只将计数器编码为这一个整数的位。从所有位设置为1开始。当您在输入数组中遇到数字n时,切换第n位。最后剩下的所有位都表示偶数次遇到的3个数字。

票数 4
EN

Stack Overflow用户

发布于 2016-01-27 03:06:35

你对问题的概述和例子不匹配。你说你在你的问题中寻找3个整数,但是这个例子显示了4。

我不确定如果没有额外的限制,这是不可能的。在我看来,最坏的情况下,长度复杂度将始终至少是O(N-6) => O(N),没有排序列表,并且具有完整的整数集。

如果我们从排序数组开始,那么是的,很简单,但是这个约束没有指定。自己对数组进行排序将会在时间或空间上过于复杂。

票数 0
EN
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接:

https://stackoverflow.com/questions/34818865

复制
相关文章

相似问题

领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档