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

文化传播集团网站建设网络营销方案策划案例

文化传播集团网站建设,网络营销方案策划案例,decorum wordpress,wordpress主题缺少style.css样式表给一个已经排好序的升序数组,其中每个元素都会重复2次,只有一个元素只有一个, 找出这个只有一个的元素。 要求时间复杂度在O(logn), 空间复杂度在O(1). 思路: 时间复杂度为O(logn), 让人想到了binary search. 因为时间复杂度为…

在这里插入图片描述

给一个已经排好序的升序数组,其中每个元素都会重复2次,只有一个元素只有一个,
找出这个只有一个的元素。
要求时间复杂度在O(logn), 空间复杂度在O(1).

思路:

时间复杂度为O(logn), 让人想到了binary search.

因为时间复杂度为O(1), 所以不能用一个数组来保存每个元素出现的次数。

不过,每个元素也就出现2次,而且是排好序的,也就是说相同的元素都是在一起的。
可以用一个cnt, 元素第一次出现时cnt = 1, 第2次出现时cnt = 0,
那么只出现一次的元素,cnt就无法清0,于是就被找出来了。
但是这种方法需要遍历数组,时间复杂度为O(n), 也能通过测试。

    public int singleNonDuplicate(int[] nums) {int cnt = 1;int n = nums.length;if(n == 1) return nums[0];for(int i = 1; i < n; i++) {if(nums[i] != nums[i-1]) {if(cnt == 1) return nums[i-1];else cnt = 1;} else {cnt = 0;}}return nums[n-1];}

下面看一下binary search.

为什么能用binary search呢?
因为每个元素出现2次(长度为偶数),只有一个元素出现了1次,
包含出现了1次的元素的部分,长度一定是奇数。

我们可以判断奇数的长度出现在左边还是右边,把left, right指针卡在奇数长度的部分。

举个例子:
2,2,3,3,4
[0] [1] [2] [3] [4]
left = 0, right = 4, mid = 2
右半边的长度(不含mid本身)为right - mid = 2, 长度为偶数,

但是发现没有,nums[mid]和nums[mid+1]两个数是一样的,
现在的长度right-mid 把两个相同的元素拆开了,违背了刚才判断的标准,
2个相同的元素都在一起才符合长度为偶数的标准,拆开了就不能按照长度为奇偶来判断了。

所以要比较nums[mid]和nums[mid+1]两个元素,如果相同,把nums[mid]也算进右边,
所以现在右边长度为奇数,可以判断单个的元素在右边,移动left = mid + 2(跳过重复元素)。
那如果是下面的例子:
1,2,2,3,3,
可以看到右边长度为偶数,这时要移动right = mid - 2(跳过重复元素)

直到nums[mid] 和 nums[mid + 1], nums[mid-1]都不相等, 返回nums[mid].

    public int singleNonDuplicate(int[] nums) {int n = nums.length;if(n == 1) return nums[0];int left = 0;int right = n - 1;while(left <= right) {int mid = left + (right - left)/2;boolean isEvenLen = ((right - mid) % 2 == 0);if(mid >= 1 && nums[mid] == nums[mid-1]) {if(isEvenLen) right = mid-2;else left = mid + 1;//重复元素算进右边长度} else if(mid < n - 1 && nums[mid] == nums[mid+1]) {if(isEvenLen) left = mid + 2; //算进重复元素后,右边长度为奇数,单个元素在右边else right = mid - 1;} else {return nums[mid];}}return -1;}
http://www.ritt.cn/news/22046.html

相关文章:

  • 网站底部样式百度权重1
  • 现代化专业群建设网站某网站搜索引擎优化
  • 学习建站的网站夫唯老师seo
  • 广州红盾信息门户网站东莞seo建站如何推广
  • 网站制作网站开发ple id充值百度交易平台官网
  • 椒江网站制作网站建设策划书
  • 重庆南岸营销型网站建设公司推荐seo产品优化免费软件
  • 个人软件外包接单平台宁波网站制作优化服务公司
  • 华为云域名注册seo学徒
  • 关于做花茶网站的策划书网站查询域名入口
  • 嘉兴高端网站建设有限公司女装关键词排名
  • 网站建设网站自助建设信息流优化师工作内容
  • 网络安全网站游戏广告联盟平台
  • qq推广开通南宁百度seo推广
  • 58同城青岛网站建设新冠疫情最新消息
  • 国外经典手机网站设计东莞百度推广排名
  • 江西头条新闻今天seo技术培训沈阳
  • 湛江专门做网站今日新闻头条最新消息
  • 网站内部资源推广牛排seo系统
  • qq怎么做自己的网站seo是什么职务
  • 网站建设和seo的工作好不好安阳企业网站优化外包
  • 网站建设价钱最新疫情最新消息
  • 高端html5网站建设织梦模板营业推广的目标通常是
  • 湖南的商城网站建设关键词seo价格
  • 长沙 网站开发报价排名优化哪家专业
  • 网站后台登陆路径登封网络推广公司
  • wordpress禁用谷歌的插件合肥网站seo整站优化
  • 聚名网域名转出搜狗搜索引擎优化指南
  • 潍坊网站建设wf3网片
  • php旅游网站开发背景电商运营培训机构哪家好