[剑指 Offer 第 2 版第 56 题] “数字在排序数组中出现的次数”做题记录

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

传送门：数组中只出现一次的两个数字，牛客网 online judge 地址。

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

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

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

样例：

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

输出：[1,2]

思路：==按位分组==。

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)

作者：liweiwei1419

来源：https://liweiwei1419.github.io/sword-for-offer/