宁德营销型网站建设,动态图片制作,wordpress 设置显示中文字体,wordpress写文章字体颜色怎么调问题描述
小R从班级中抽取了一些同学#xff0c;每位同学都会给出一个数字。已知在这些数字中#xff0c;某个数字的出现次数超过了数字总数的一半。现在需要你帮助小R找到这个数字。 测试样例
样例1#xff1a; 输入#xff1a;array [1, 3, 8, 2, 3, 1, 3, 3, 3] 输出…问题描述
小R从班级中抽取了一些同学每位同学都会给出一个数字。已知在这些数字中某个数字的出现次数超过了数字总数的一半。现在需要你帮助小R找到这个数字。 测试样例
样例1 输入array [1, 3, 8, 2, 3, 1, 3, 3, 3] 输出3 样例2 输入array [5, 5, 5, 1, 2, 5, 5] 输出5 样例3 输入array [9, 9, 9, 9, 8, 9, 8, 8] 输出9 方法
摩尔投票算法 是解决这个问题的一种高效算法。这个算法的核心思想是通过“投票”的方式逐步排除掉不可能的候选数字最终得到一个出现次数最多的数字。由于题目中说明有一个数字的出现次数超过了数组的一半因此摩尔投票算法能够有效解决问题。
摩尔投票算法的工作原理 投票阶段首先选择一个候选数字并将它的票数初始化为 1。然后遍历数组中的每个数字 如果当前数字和候选数字相同票数加 1。如果当前数字和候选数字不同票数减 1。如果票数减为 0则选取当前数字作为新的候选数字并将票数重置为 1。 确认阶段在摩尔投票阶段结束后我们得到一个候选数字。由于题目保证有一个数字出现次数超过数组总数的一半因此最后的候选数字就是我们要找的数字。
代码实现: 代码解释 摩尔投票算法 我们使用 candidate 来记录当前的候选数字count 来记录候选数字的票数。如果票数为零说明之前的候选数字被“淘汰”了我们就将当前数字设为新的候选数字并将票数设为 1。如果当前数字与候选数字相同票数加 1。如果当前数字与候选数字不同票数减 1。 保证正确性 根据题目描述存在一个数字的出现次数超过数组总长度的一半因此最终的 candidate 一定是正确的数字。
时间复杂度
时间复杂度O(N)其中 N 是数组的长度。我们只需要遍历数组一次来找到候选数字。空间复杂度O(1)只用了常数空间。
测试用例 输入[1, 3, 8, 2, 3, 1, 3, 3, 3] 输出33 出现了 5 次超过了一半。 输入[5, 5, 5, 1, 2, 5, 5] 输出55 出现了 5 次超过了一半。 输入[9, 9, 9, 9, 8, 9, 8, 8] 输出99 出现了 5 次超过了一半。
