相关疑难解决方法(0)

编辑:对于这个问题的新手,我已经发布了一个答案,澄清了发生了什么.接受的答案是我认为最能回答我最初发布的问题的答案,但有关详细信息,请参阅我的答案.

注意:此问题最初是伪代码和使用列表.我已将它改编为Java和数组.因此,虽然我很想看到任何使用Java特定技巧的解决方案(或任何语言的技巧!),但请记住原始问题与语言无关.

问题

比方说,有两个未排序整型数组a和b,以允许元素的重复.它们是相同的(关于包含的元素),除了一个数组有一个额外的元素.举个例子:

int[] a = {6, 5, 6, 3, 4, 2};
int[] b = {5, 7, 6, 6, 2, 3, 4};

设计一种算法,将这两个数组作为输入并输出单个唯一整数(在上例中为7).

解决方案(迄今为止)

我想出了这个:

public static int getUniqueElement(int[] a, int[] b) {
    int ret = 0;
    for (int i = 0; i < a.length; i++) {
        ret ^= a[i];
    }
    for (int i = 0; i < b.length; i++) {
        ret ^= b[i];
    }
    return ret;
}

课堂上提出的"官方"解决方案:

public static …

在长度为n的序列中,其中n = 2k + 3,即有k个唯一数字出现两次,并且三个数字仅出现一次.

问题是:如何找到仅出现一次的三个唯一数字？

例如,在顺序1 1 2 6 3 6 5 7 7中,三个唯一数字是2 3 5.

注意:3 <= n <1e6,数字范围为1到2e9

内存限制:1000KB,这意味着我们无法存储整个序列.

方法我试过(内存限制超过)？

我初始化一个树,当读入一个数字时,我尝试将其从树中删除,如果remove返回false(未找到),我将它添加到树中.最后,树有三个数字.它工作,但内存限制超过.

我知道如何使用位操作找到一个或两个这样的数字.所以我想知道是否

我们可以找到三个使用相同的方法(或一些类似的方法)？

找到一个/两个数字的方法只出现一次:

如果只有一个数字出现一次,我们可以对序列应用XOR来找到它.

如果有两个,我们可以先对序列应用XOR,然后将序列分成2个部分,结果为1,然后再将XOR应用于2个部分,我们将找到答案.

给定一个整数数组,找到第一个唯一的整数.

我的解决方案:使用 std::map

将整数(数字作为键,其索引作为值)逐个放入(O(n^2 lgn)),如果有重复,则从地图中删除条目(O(lg n)),将所有数字放入地图后,迭代地图并找到索引最小的键O(n ).

O(n^2 lgn) 因为地图需要做排序.

效率不高.

更好的解决方案？

今天上课时我们被要求写一个算法.

给定一个数组,删除重复值:

• 它应该是稳定的,不应该使用内循环.
• 应该尽可能地到位
• 不使用内置函数(我只允许使用.push)

在与它摔跤一段时间之后,这就是我想出来的.

function remove_dupes(arr){
  var seen = {};
  var count = 0;

  for( var i = 0; i < arr.length - count ; i++) {
    arr[i] = arr[i+count];

    if( seen[arr[i]] ) {
      count++;
      arr[i] = arr[i+count];
      i--;
    }

    seen[arr[i]] = true;
  }

  arr.length = arr.length - count;
}

工作JSBin

我在这里有一些重复的代码,我觉得这可能i--不是最好的方法.

有什么方法可以改进这个代码(不使用内置函数)？