当前位置: 首页 > news >正文

报纸做网站宣传费用营销型网站名词解释

报纸做网站宣传费用,营销型网站名词解释,网站重新建设的通知,开发工具都有什么leetcode_169. 多数元素 问题描述 给定一个大小为 n 的数组 nums ,返回其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。你可以假设数组是非空的,并且给定的数组总是存在多数元素。 示例 1: 输入: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.length
  • 1 <= 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个候选人($ 0<=i<n ) 他们都有 )他们都有 )他们都有arr[i]$个支持者, 在竞选中, 每个支持者可以为自己支持的候选人投支持票, 同样也可以为自己不支持的候选人投反对票(每个人都只能有一个支持的候选人, 且每个人都能投一次票, 无论是支持还是反对). 这时, 有一个天降猛男**“甲”, 支持者超过了 50 % 50\% 50%, 那么请问, 如果其他候选者联合起来给甲"捣乱", 比如某几个候选人串通, 让他们的支持者去给甲**投反对票, 或者把票都投给某一个""以外的候选者, 能不能对竞选结果产生影响呢?

显然不能, 因为甲的支持者是超过 50 % 50\% 50%的, 哪怕就超过一个人也是一样, 甲是 100 % 100\% 100% 会赢的, 无论其他人怎么操作. 就算剩下的所有的候选人支持者都把票投给一个人, 也不会超过.

在上面那个例子里, 就是我们的多数元素, 甲的支持者的数量就是多数元素出现的次数,

为了实现上面的算法, 我们需要维护两个变量, 一个res记录候选的多数元素和它出现的次数count, 一开始count为0, res记录数组的第一个元素, 随后每当遇到一个与当前res相同的 就执行count++, 否则就count--, 当count==0时, 就改变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(vector<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;}
};
http://www.mmbaike.com/news/55898.html

相关文章:

  • 深圳南山网站建设工作室中国万网官网
  • 定制企业网站费用今天中国新闻
  • 网站建设功能清单软文代写平台有哪些
  • 淘宝优惠劵网站怎么做全网营销渠道
  • 福州网站建设信息外包接单平台
  • 怎样查看网站的权重网站优化排名
  • tp框架做商城网站怎么用缓存seo网络优化日常工作内容
  • 龙湖镇华南城网站建设如何网络营销自己的产品
  • sns社交网站开发潍坊seo招聘
  • 秦皇岛市做公司网站的网络营销有哪些内容
  • wordpress站外搜索百度竞价外包
  • 建设通破解vip网站关键词优化工具
  • wordpress采集网站网页模板代码
  • 青岛做网站哪家专业中国搜索
  • 北京旗网站制作搜索百度
  • 做网站要注意哪些问题seo的内容怎么优化
  • 做网站后付款武汉网优化seo公司
  • 龙海市建设局网站服装品牌营销策划方案
  • 企业做网站需要的资料谷歌引擎搜索
  • 做网站费用 会计分录百度竞价开户哪家好
  • 做条形图的网站百度公司全称叫什么
  • 浙江省城乡住房建设部网站合肥网络推广公司
  • 产品做推广都有那些网站深圳外贸网络推广
  • 商城网站源码下载深圳外贸网站推广
  • 网站建设网页设市场营销教材电子版
  • 如何查到别人的网站做哪些竞价词搜索引擎是什么意思啊
  • wordpress 文件夹改名惠州seo网站推广
  • 做外贸网站有什么用百度收录站长工具
  • b2b网站如何做推广湖南靠谱关键词优化
  • 谷城网站建设做一个简单网页