为什么我的配对查找器的复杂性很差以及需要改进的地方

Question

正在完成这个挑战，但由于我的解决方案的复杂性，我最终得分很差，我得到了一个结果，但我不知道为什么，因为我觉得它应该运行得更快，而且代码明智，它非常紧凑和高效：任务简介： O(n2)

我被要求做什么：

我的代码如下：

import java.util.LinkedList;

class Solution {
    public int solution(int[] A) {
        LinkedList <Integer> checkedNumbers = new LinkedList<Integer>();
        for (int i=0; i< A.length; i++) {
            // check against what we have found before
            boolean foundNumber = false;
            for(int x=0; x <checkedNumbers.size(); x++) {
                if (A[i] == checkedNumbers.get(x)) {
                    checkedNumbers.remove(x);
                    foundNumber = true;
                    break;
                }
            }
            if(foundNumber == false) {
                checkedNumbers.add(A[i]);
            }
        }
        int result = checkedNumbers.pop();
        return result ;
    }

}

Answer 1

有一个技巧可以在没有任何复杂数据结构的情况下解决这个问题：

int v = 0;
for (int a : A) {
  v ^= a; // Compound exclusive or.
}
return v;

此处使用的复合异或赋值运算符将“翻转”v对应于 中值为 1 的位的位a。

这是有效的，因为a ^ a ? 0(and a ^ b ? b ^ a, and (a ^ b) ^ c ? a ^ (b ^ c), and a ^ 0 ? a)，所以a第一次观察的位被a第二次观察的位抵消。

最后将设置的唯一位v是来自未配对元素的位。

例如，如果数组包含[a, b, a, b, u]（u未配对的元素也是如此）：

  a ^ b ^ a ^ b ^ u
= (a ^ a) ^ (b ^ b) ^ u
= 0 ^ 0 ^ u
= u