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

[剑指 Offer 第 2 版第 39 题] “数组中出现次数超过一半的数字”做题记录

[剑指 Offer 第 2 版第 39 题] “数组中出现次数超过一半的数字”做题记录

第 39 题:数组中超过一半的数字

传送门: 数组中出现次数超过一半的数字牛客网 online judge 地址

数组中有一个数字出现的次数超过数组长度的一半,请找出这个数字。

假设数组非空,并且一定存在满足条件的数字。

思考题

  • 假设要求只能使用 O(n) 的时间和额外 O(1) 的空间,该怎么做呢?

样例:

输入:[1,2,1,1,3]

输出:1

思路1:首先排序,中间那个数,一定是要求的。

思路2:将首次出现的数 count + 1,与之后的数进行比较,相等则 +1,否则 -1,最后进行校验是否超过长度的一半。数组中有一个数字出现的次数超过数组长度的一半,也就是说它出现的次数比其他所有数字出现次数的和还要多。因此我们可以考虑在遍历数组的时候保存两个值:一个是数组的一个数字,一个是次数。当我们遍历到下一个数字的时候,如果下一个数字和我们之前保存的数字相同,则次数加 1;如果下一个数字和我们之前保存的数字不同,则次数减 1 。如果次数为零,我们需要保存下一个数字,并把次数设为 1。由于我们要找的数字出现的次数比其他所有数字出现的次数之和还要多,那么要找的数字肯定是最后一次把次数设为 1 时对应的数字。

Python 代码:

  # -*- coding:utf-8 -*-
    class Solution:
        def MoreThanHalfNum_Solution(self, numbers):
            res = numbers[0]
            times = 1
            for num in numbers[1:]:
                if times == 0:
                    res = num
                    times = 1
                elif res == num:
                    times += 1
                else:
                    times -= 1
            # 验证 res 是不是超过一半
            times = 0
            for num in numbers:
                if num == res:
                    times += 1
            return res if times > len(numbers) // 2 else 0


说明:“假设数组非空,并且一定存在满足条件的数字。”的时候,就不用做最后一步的判断。

Python 代码:

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

            l = len(nums)
            if l == 1:
                return nums[0]

            num = nums[0]
            times = 1
            for i in range(1, l):
                # 注意分类讨论的顺序,先看次数是不是 0
                # 以下的 3 种情况是互斥的
                if times == 0:
                    num = nums[i]
                    times += 1
                elif num == nums[i]:
                    times += 1
                else:
                    times -= 1
            return num

C++ 代码:

liwei2019101114_1.png

Java 代码:

  import java.util.Arrays;

    public class Solution {
        //
        // {1,2,3,2,2,2,5,4,2} 9 4
        // {1,2,3,2,2,2,5,4} 8 4
        public int MoreThanHalfNum_Solution(int[] array) {
            int len = array.length;
            if (len == 0) {
                return 0;
            }
            Arrays.sort(array);
            int target = array[len / 2];
            int count = 0;
            for (int i = 0; i < len; i++) {
                if (array[i] == target) {
                    count++;
                }
            }
            if (count > len / 2) {
                return target;
            }
            return 0;
        }


        public static void main(String[] args) {
            int[] nums = new int[]{1, 2, 3, 2, 2, 2, 5, 4, 2};
            // [1,2,3,2,4,2,5,2,3]
            Solution solution = new Solution();
            int moreThanHalfNum_solution = solution.MoreThanHalfNum_Solution(nums);
            System.out.println(moreThanHalfNum_solution);
        }
    }

作者:liweiwei1419

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


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

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

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

标题:[剑指 Offer 第 2 版第 39 题] “数组中出现次数超过一半的数字”做题记录

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

« [剑指 Offer 第 2 版第 38 题] “字符串的排列”做题记录
[剑指 Offer 第 2 版第 40 题] “最小的 K 个数”做题记录»

相关推荐

QR code