《剑指 Offer （第 2 版）》第 56 题：数组中只出现一次的两个数字

第 56-1 题：数组中只出现一次的两个数字

一个整型数组里除了两个数字之外，其他的数字都出现了两次。

请写程序找出这两个只出现一次的数字。

你可以假设这两个数字一定存在。

样例：

输入： $[1,2,3,3,4,4]$

输出： $[1,2]$

思路：按位分组。这道题有一定技巧性。

补充说明：^：按位异或运算符：当两对应的二进位相异时，结果为 $1$ ，可以记忆为“无符号加法”。

Python 代码：

class Solution(object):
    def findNumsAppearOnce(self, nums):
        """
        :type nums: List[int]
        :rtype: List[int]
        """
        l = len(nums)
        if l < 2:
            raise Exception('程序出错')
        if l == 2:
            return nums

        # 全部相与一遍
        xor = 0
        for num in nums:
            xor ^= num
            
        # 最末尾的 1 从右向左边数在第几位
        counter = 0
        while xor & 1 == 0:
            xor >>= 1
            counter += 1

        res = [0, 0]
        for num in nums:
            if (num >> counter) & 1 == 1:
                res[1] ^= num
            else:
                res[0] ^= num
        return res

Java 代码：

import java.util.Arrays;

// 第 56 题：数组中数字出现的次数 P275
// 参考资料：
// 1、https://blog.csdn.net/derrantcm/article/details/46771717
public class Solution {

    // 考察位运算：或、与、异或、非，以及无符号左移 >>>
    public int[] findNumbersAppearanceOnce(int[] nums) {
        int len = nums.length;
        int[] res = new int[2];
        assert len >= 2;
        if (len == 2) {
            return nums;
        }
        // 那两个只出现一次的数的异或运算的结果
        int xor = xor(nums);
        
        // 关键在这里
        // 找到这个 xor 的二进制表示第 1 个是 1 的数位是第几位
        int binaryFirstNotZero = binaryFirstNotZero(xor);
        
        // 接下来分别对两组进行异或
        for (int i = 0; i < len; i++) {
            // 如果这个数右移这么多位是 1 的分在一组，是 0 的分在另外一组，遍历的时候，就进行异或运算
            if ((nums[i] >>> binaryFirstNotZero & 1) == 1) {
                res[0] ^= nums[i];
            } else {
                res[1] ^= nums[i];
            }
        }
        return res;
    }

    // 得到一个数组经过异或运算的结果 xor
    // 异或 的英文翻译就是 xor
    private int xor(int[] nums) {
        int xor = 0;
        for (int i = 0; i < nums.length; i++) {
            xor ^= nums[i];
        }
        return xor;
    }

    // 得到一个整数的二进制表示从右到左第 1 个非零的位数是第几位
    private int binaryFirstNotZero(int num) {
        int index = 0;
        // 这里的 1 把它看成二进制的 1，即 00000001
        while ((num & 1) == 0 && index < 32) {
            num >>>= 1;
            index++;
        }
        // 走到这里满足 (num & 1) == 1
        return index;
    }

    public static void main(String[] args) {
        int[] nums = {2, 4, 3, 6, 3, 2, 5, 5};
        Solution solution = new Solution();
        int[] res = solution.findNumbersAppearanceOnce(nums);
        System.out.println(Arrays.toString(res));

        int[] nums2 = {2, 4, 3, 6, 3, 2, 5, 5};
        int[] res2 = solution.findNumbersAppearanceOnce(nums2);
        System.out.println(Arrays.toString(res2));

        int[] nums3 = {4, 6};
        int[] res3 = solution.findNumbersAppearanceOnce(nums3);
        System.out.println(Arrays.toString(res3));

        int[] nums4 = {4, 6, 1, 1, 1, 1};
        int[] res4 = solution.findNumbersAppearanceOnce(nums4);
        System.out.println(Arrays.toString(res4));
    }
}

0 到 n-1 中缺失的数字

传送门：0 到 n-1 中缺失的数字。

一个长度为 n-1 的递增排序数组中的所有数字都是唯一的，并且每个数字都在范围 0 到 n-1 之内。

在范围 0 到 n-1 的 n 个数字中有且只有一个数字不在该数组中，请找出这个数字。

样例
输入：[0,1,2,4]

输出：3

思路：典型的使用“二分法”解决的问题。

Python 代码：

class Solution(object):
    def getMissingNumber(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """

        size = len(nums)
        l = 0
        r = size

        while l < r:

            mid = l + (r - l) // 2
            if nums[mid] > mid:
                # [0,1,2,3,4,6]
                # mid 有可能是要求的数
                r = mid
            else:
                assert nums[mid] <= mid
                l = mid + 1
        return l


if __name__ == '__main__':
    solution = Solution()
    nums = [0, 1, 2, 4]
    result = solution.getMissingNumber(nums)
    print(result)

数组中数值和下标相等的元素

传送门：数组中数值和下标相等的元素。

假设一个单调递增的数组里的每个元素都是整数并且是唯一的。

请编程实现一个函数找出数组中任意一个数值等于其下标的元素。

例如，在数组 $[-3, -1, 1, 3, 5]$ 中，数字 $3$ 和它的下标相等。

样例：

输入： $[-3, -1, 1, 3, 5]$

输出： $3$

注意：如果不存在，则返回 $-1$ 。

思路：典型的使用“二分法”解决的问题。

Python 代码：

class Solution(object):
    def getNumberSameAsIndex(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """

        # 使用二分法
        size = len(nums)
        l = 0
        r = size - 1

        while l < r:
            mid = l + (r - l) // 2
            if nums[mid] < mid:
                l = mid + 1
            else:
                assert nums[mid] >= mid
                r = mid
        return l if nums[l] == l else -1

第 56-2 题：数组中唯一只出现一次的数字

传送门：数组中唯一只出现一次的数字。

在一个数组中除了一个数字只出现一次之外，其他数字都出现了三次。

请找出那个只出现一次的数字。

你可以假设满足条件的数字一定存在。

思考题：

如果要求只使用 $O(n)$ 的时间和额外 $O(1)$ 的空间，该怎么做呢？

样例：
输入：[1,1,1,2,2,2,3,4,4,4]

输出：3

思路：限制在 $O(1)$ 空间复杂度，那就只有通过二进制，一位一位去看了。

Python 代码：

class Solution(object):
    def findNumberAppearingOnce(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """

        res = 0

        for i in range(32):
            count = 0
            for num in nums:
                # 不要忘记 & 1
                if (num >> i) & 1:
                    count += 1
            if count % 3:
                res += 1 << i
        return res


if __name__ == '__main__':
    nums = [1, 0, 0, 0, 2, 1, 1]
    solution = Solution()
    result = solution.findNumberAppearingOnce(nums)
    print(result)