1. 首页
  2. 剑指offer经典面试题

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

[剑指 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/


JS中文网,Javascriptc中文网是中国领先的新一代开发者社区和专业的技术媒体,一个帮助开发者成长的社区,是给开发者用的 Hacker News,技术文章由为你筛选出最优质的干货,其中包括:Android、iOS、前端、后端等方面的内容。目前已经覆盖和服务了超过 300 万开发者,你每天都可以在这里找到技术世界的头条内容。

本文著作权归作者所有,如若转载,请注明出处

转载请注明:文章转载自「 Java极客技术学习 」https://www.javajike.com

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

链接:https://www.javajike.com/article/3300.html

« [剑指 Offer 第 2 版第 54 题] “二叉搜索树的第k个结点”做题记录
[剑指 Offer 第 2 版第 61 题] “n 个骰子的点数”做题记录»

相关推荐

QR code