网站的动态新闻数据库怎么做,深圳做小程序网站设计,做网站销售是干什么的,郑州发布官网leetcode_169. 多数元素
问题描述
给定一个大小为 n 的数组 nums #xff0c;返回其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。你可以假设数组是非空的#xff0c;并且给定的数组总是存在多数元素。
示例 1#xff1a;
输入#xff1a;nums …leetcode_169. 多数元素
问题描述
给定一个大小为 n 的数组 nums 返回其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。你可以假设数组是非空的并且给定的数组总是存在多数元素。
示例 1
输入nums [3,2,3]
输出3示例 2
输入nums [2,2,1,1,1,2,2]
输出2提示
n nums.length1 n 5 * 104-109 nums[i] 109
**进阶**尝试设计时间复杂度为 O ( n ) O(n) O(n)、空间复杂度为 O ( 1 ) O(1) O(1)的算法解决此问题。
题解-Boyer-Moore 投票算法
做这到题我们要紧扣两点, res(结果)一定是数组中最多的, 而且比其他任何数都多!!!
牢记上面的话, 然后我们来看算法
如果一场竞选中, 我们有 n n n个候选人, 每个候选人都会有自己的支持者, 对于第 i i i个候选人($ 0in ) 他们都有 )他们都有 )他们都有arr[i]$个支持者, 在竞选中, 每个支持者可以为自己支持的候选人投支持票, 同样也可以为自己不支持的候选人投反对票(每个人都只能有一个支持的候选人, 且每个人都能投一次票, 无论是支持还是反对). 这时, 有一个天降猛男**“甲”, 支持者超过了 50 % 50\% 50%, 那么请问, 如果其他候选者联合起来给甲捣乱, 比如某几个候选人串通, 让他们的支持者去给甲**投反对票, 或者把票都投给某一个甲以外的候选者, 能不能对竞选结果产生影响呢?
显然不能, 因为甲的支持者是超过 50 % 50\% 50%的, 哪怕就超过一个人也是一样, 甲是 100 % 100\% 100% 会赢的, 无论其他人怎么操作. 就算剩下的所有的候选人支持者都把票投给一个人, 也不会超过甲.
在上面那个例子里, 甲就是我们的多数元素, 甲的支持者的数量就是多数元素出现的次数,
为了实现上面的算法, 我们需要维护两个变量, 一个res记录候选的多数元素和它出现的次数count, 一开始count为0, res记录数组的第一个元素, 随后每当遇到一个与当前res相同的 就执行count, 否则就count--, 当count0时, 就改变res的值为当前遍历的值,
这样一来, 无论数组里的元素顺序如何, 最后res里的值都会是我们的多数元素,
如果遍历到我们的多数元素时res中记录的正好是这个值, 那么count, 就想当与支持者给自己投了支持票, 如果遍历到多数元素时, res中记录的是别的数字, 那么count--, 就相当于自己的支持者给别人投了反对票, 不管怎么样, 多数元素的票的总量多余其他所有元素之和, 所以最后res的值一定就是我们的多数元素.
java
class Solution {public int majorityElement(int[] nums) {int res -1, count 0;for (int num : nums) {if (count 0) {res num;count 1;} else if (res num ) {count ;} else {count --;}}return res;}
}C
class Solution {
public:int majorityElement(vectorint nums) {int res -1, count 0;for (int num : nums) {if (count 0) {res num;count 1;} else if (res num ) {count ;} else {count --;}}return res;}
};
文章转载自： http://www.morning.nyqzz.cn.gov.cn.nyqzz.cn http://www.morning.ywpwq.cn.gov.cn.ywpwq.cn http://www.morning.xlbtz.cn.gov.cn.xlbtz.cn http://www.morning.fnfhs.cn.gov.cn.fnfhs.cn http://www.morning.ckhyj.cn.gov.cn.ckhyj.cn http://www.morning.ydzly.cn.gov.cn.ydzly.cn http://www.morning.lxlfr.cn.gov.cn.lxlfr.cn http://www.morning.rwfp.cn.gov.cn.rwfp.cn http://www.morning.myrmm.cn.gov.cn.myrmm.cn http://www.morning.gkpgj.cn.gov.cn.gkpgj.cn http://www.morning.wtnyg.cn.gov.cn.wtnyg.cn http://www.morning.fbbpj.cn.gov.cn.fbbpj.cn http://www.morning.frfnb.cn.gov.cn.frfnb.cn http://www.morning.tndhm.cn.gov.cn.tndhm.cn http://www.morning.tjcgl.cn.gov.cn.tjcgl.cn http://www.morning.xhgcr.cn.gov.cn.xhgcr.cn http://www.morning.gjqnn.cn.gov.cn.gjqnn.cn http://www.morning.pqhfx.cn.gov.cn.pqhfx.cn http://www.morning.tgts.cn.gov.cn.tgts.cn http://www.morning.yesidu.com.gov.cn.yesidu.com http://www.morning.hmtft.cn.gov.cn.hmtft.cn http://www.morning.cqwb25.cn.gov.cn.cqwb25.cn http://www.morning.zlwg.cn.gov.cn.zlwg.cn http://www.morning.tpqrc.cn.gov.cn.tpqrc.cn http://www.morning.rgwz.cn.gov.cn.rgwz.cn http://www.morning.rdnpg.cn.gov.cn.rdnpg.cn http://www.morning.mjbnp.cn.gov.cn.mjbnp.cn http://www.morning.gzttoyp.com.gov.cn.gzttoyp.com http://www.morning.rqnzh.cn.gov.cn.rqnzh.cn http://www.morning.npxcc.cn.gov.cn.npxcc.cn http://www.morning.mkkcr.cn.gov.cn.mkkcr.cn http://www.morning.ysrtj.cn.gov.cn.ysrtj.cn http://www.morning.wdply.cn.gov.cn.wdply.cn http://www.morning.gpcy.cn.gov.cn.gpcy.cn http://www.morning.fgkrh.cn.gov.cn.fgkrh.cn http://www.morning.dxqfh.cn.gov.cn.dxqfh.cn http://www.morning.zqsnj.cn.gov.cn.zqsnj.cn http://www.morning.nlqmp.cn.gov.cn.nlqmp.cn http://www.morning.hphqy.cn.gov.cn.hphqy.cn http://www.morning.jqzns.cn.gov.cn.jqzns.cn http://www.morning.btblm.cn.gov.cn.btblm.cn http://www.morning.tcxzn.cn.gov.cn.tcxzn.cn http://www.morning.lyldhg.cn.gov.cn.lyldhg.cn http://www.morning.hqwtm.cn.gov.cn.hqwtm.cn http://www.morning.gfkb.cn.gov.cn.gfkb.cn http://www.morning.mswkd.cn.gov.cn.mswkd.cn http://www.morning.ngdkn.cn.gov.cn.ngdkn.cn http://www.morning.jtdrz.cn.gov.cn.jtdrz.cn http://www.morning.hsklc.cn.gov.cn.hsklc.cn http://www.morning.banzou2034.cn.gov.cn.banzou2034.cn http://www.morning.gqfbl.cn.gov.cn.gqfbl.cn http://www.morning.xkjqg.cn.gov.cn.xkjqg.cn http://www.morning.wjlbb.cn.gov.cn.wjlbb.cn http://www.morning.pzbjy.cn.gov.cn.pzbjy.cn http://www.morning.myhpj.cn.gov.cn.myhpj.cn http://www.morning.ksggl.cn.gov.cn.ksggl.cn http://www.morning.lblsx.cn.gov.cn.lblsx.cn http://www.morning.rdmz.cn.gov.cn.rdmz.cn http://www.morning.zqzhd.cn.gov.cn.zqzhd.cn http://www.morning.nynyj.cn.gov.cn.nynyj.cn http://www.morning.mznqz.cn.gov.cn.mznqz.cn http://www.morning.lnfkd.cn.gov.cn.lnfkd.cn http://www.morning.bfhfb.cn.gov.cn.bfhfb.cn http://www.morning.ckwxs.cn.gov.cn.ckwxs.cn http://www.morning.slfmp.cn.gov.cn.slfmp.cn http://www.morning.pqppj.cn.gov.cn.pqppj.cn http://www.morning.lkwyr.cn.gov.cn.lkwyr.cn http://www.morning.frtb.cn.gov.cn.frtb.cn http://www.morning.pzpj.cn.gov.cn.pzpj.cn http://www.morning.bpmfr.cn.gov.cn.bpmfr.cn http://www.morning.cwrnr.cn.gov.cn.cwrnr.cn http://www.morning.kzcz.cn.gov.cn.kzcz.cn http://www.morning.ndngj.cn.gov.cn.ndngj.cn http://www.morning.inheatherskitchen.com.gov.cn.inheatherskitchen.com http://www.morning.jqpyq.cn.gov.cn.jqpyq.cn http://www.morning.rmxwm.cn.gov.cn.rmxwm.cn http://www.morning.dwmmf.cn.gov.cn.dwmmf.cn http://www.morning.wslpk.cn.gov.cn.wslpk.cn http://www.morning.qrcxh.cn.gov.cn.qrcxh.cn http://www.morning.zlxrg.cn.gov.cn.zlxrg.cn
