找到成对或三元组中单个数字的最佳方法

Question

因为这是一系列问题中的一个问题.我正在修改它以使其不与其他的重复.谢谢你的帮助.

对:我有一个整数数组.在数组中,除了一个元素外,每个元素都会出现两次.我想找到那个单号.

示例:[2, 4, 2, 1, 4, 1, 3],单个数字是3.

我的想法是使用a HashMap,这需要O(n)时间和O(n)空间.还有更好的解决方案吗？谢谢.

三元组:每个元素出现三次,除了一个.找一个单一的.

示例:[1, 2, 4, 2, 4, 1, 2, 4, 1, 3],单个数字是3.

Answer 1

考虑以"位"方式解决它,这需要O(n)时间和O(1)空间:

public class Solution {
    public int singleNumber(int[] A) {
        if (A.length==0) return 0;
        if (A.length==1) return A[0];

        int result = A[0];

        for (int i=1; i<A.length; i++) {
            result = result ^ A[i];
        }

        return result;         
    }
}

嗯,是的,我也有解决方案,找到三元组的单一.

public class Solution {
    public int singleNumber(int[] A) {
        int result = 0;

        for (int i = 0; i < 32; i++) {
            int curr = 0;
            for (int num : A) {
                curr += (num >> i) & 1;
            }
            result += (curr % 3) << i;
        }

        return result;
    }
}

这对您来说可能更难理解.请阅读一些有关位操作的资料,然后弄清楚此解决方案的工作原理.