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

做培训的网站建设温州seo推广外包

做培训的网站建设,温州seo推广外包,给人做网站能赚钱吗,多商家平台原题链接🔗:在排序数组中查找元素的第一个和最后一个位置 难度:中等⭐️⭐️ 题目 给你一个按照非递减顺序排列的整数数组 nums,和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。 如果数组中不存在目标…

原题链接🔗:在排序数组中查找元素的第一个和最后一个位置
难度:中等⭐️⭐️

题目

给你一个按照非递减顺序排列的整数数组 nums,和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。

如果数组中不存在目标值 target,返回 [-1, -1]

你必须设计并实现时间复杂度为 O(log n) 的算法解决此问题。

示例 1:
输入:nums = [5,7,7,8,8,10], target = 8
输出:[3,4]

示例 2:
输入:nums = [5,7,7,8,8,10], target = 6
输出:[-1,-1]

示例 3:
输入:nums = [], target = 0
输出:[-1,-1]

提示:

  • 0 <= nums.length <= 105
  • -109 <= nums[i] <= 109
  • nums 是一个非递减数组
  • -109 <= target <= 109

二分查找

  1. 二分查找(Binary Search),也称为折半搜索,是一种在有序数组中查找特定元素的搜索算法。其基本思想是将目标值与数组中间的元素进行比较:

    1. 如果目标值等于中间元素,搜索成功,返回该位置。
    2. 如果目标值小于中间元素,搜索范围缩小至数组的左半部分。
    3. 如果目标值大于中间元素,搜索范围缩小至数组的右半部分。
    4. 这个过程将不断重复,直到找到目标值或者搜索范围为空为止。
  2. 以下是二分查找算法的一般步骤:

    1. 初始化:设置两个指针,一个指向数组的起始位置(通常记为 left),另一个指向数组的结束位置(通常记为 right)。

    2. 循环条件:当 left 小于等于 right 时,继续循环。

    3. 计算中间位置:计算 leftright 之间的中间位置 mid,通常使用 (left + right) / 2

    4. 比较与调整

      • 如果 nums[mid] 等于目标值,根据需要返回 mid 或继续搜索以找到更精确的位置。
      • 如果 nums[mid] 大于目标值,将 right 调整为 mid - 1
      • 如果 nums[mid] 小于目标值,将 left 调整为 mid + 1
    5. 循环结束:如果 left 大于 right,则表示目标值不在数组中,返回一个特定的值(通常是 -1)表示未找到。

  3. 二分查找的效率非常高,时间复杂度为 O(log n),其中 n 是数组的长度。然而,它要求数组是有序的,并且只能应用于一维有序数组。

  4. 下面是一个简单的 C++ 实现示例:

int binarySearch(const std::vector<int>& nums, int target) {int left = 0, right = nums.size() - 1;while (left <= right) {int mid = left + (right - left) / 2; // 防止溢出if (nums[mid] == target) {return mid; // 找到目标值} else if (nums[mid] < target) {left = mid + 1; // 搜索右半部分} else {right = mid - 1; // 搜索左半部分}}return -1; // 未找到目标值
}

这个函数会返回目标值在数组中的索引,如果目标值不在数组中,则返回 -1。

题解

  1. 解题思路:

LeetCode 上的这个问题通常被称为“Find First and Last Position of Element in Sorted Array”,题目编号为 34。这个问题可以通过二分查找算法来解决,因为数组是已经排序的。

以下是解决这个问题的一般思路:

  • 理解问题:首先,你需要理解问题的要求,即在一个升序排序的数组中找到给定元素的第一个和最后一个位置。

  • 二分查找:由于数组是有序的,你可以使用二分查找来找到目标元素的索引。二分查找的基本思想是将数组分成两半,比较中间元素与目标值,然后根据比较结果决定是继续在左半部分查找还是右半部分查找。

  • 找到第一个位置:使用二分查找,但需要稍作修改以找到第一个位置。在每次迭代中,如果中间元素等于目标值,你不能立即返回这个位置,因为可能还有更小的索引也是目标值。你需要向左半边继续查找。

  • 找到最后一个位置:同样使用二分查找,但这次如果中间元素等于目标值,你需要向右半边继续查找,因为可能还有更大的索引也是目标值。

  • 边界条件:在查找过程中,需要处理数组的边界条件,确保不会访问数组之外的索引。

  1. c++ demo:
#include <vector>
#include <iostream>// 二分查找函数,用于找到目标值的索引
int binarySearch(const std::vector<int>& nums, int target, bool findFirst) {int left = 0, right = nums.size() - 1, result = -1;while (left <= right) {int mid = left + (right - left) / 2;if (nums[mid] == target) {result = mid; // 记录找到的位置if (findFirst) {right = mid - 1; // 向左查找第一个位置}else {left = mid + 1; // 向右查找最后一个位置}}else if (nums[mid] < target) {left = mid + 1;}else {right = mid - 1;}}return result;
}// 主函数,用于找到元素的第一个和最后一个位置
std::vector<int> findFirstAndLastPosition(const std::vector<int>& nums, int target) {int first = binarySearch(nums, target, true); // 找到第一个位置int last = binarySearch(nums, target, false); // 找到最后一个位置return { first, last };
}int main() {std::vector<int> nums = { 5, 7, 7, 8, 8, 10 };int target = 8;std::vector<int> positions = findFirstAndLastPosition(nums, target);std::cout << "First position: " << positions[0] << std::endl;std::cout << "Last position: " << positions[1] << std::endl;return 0;
}
  • 输出结果:

First position: 3
Last position: 4

  1. 代码仓库地址:findFirstAndLastPosition

文章转载自:
http://isopod.bnpn.cn
http://anodynin.bnpn.cn
http://uricacidemia.bnpn.cn
http://worldbeater.bnpn.cn
http://tsouris.bnpn.cn
http://unholy.bnpn.cn
http://sulfuretted.bnpn.cn
http://salience.bnpn.cn
http://kelp.bnpn.cn
http://coastline.bnpn.cn
http://sliver.bnpn.cn
http://repetitious.bnpn.cn
http://armomancy.bnpn.cn
http://kymry.bnpn.cn
http://soqotra.bnpn.cn
http://metalled.bnpn.cn
http://unroll.bnpn.cn
http://lumberer.bnpn.cn
http://hobbyist.bnpn.cn
http://playgoing.bnpn.cn
http://radiolabel.bnpn.cn
http://disrate.bnpn.cn
http://spallation.bnpn.cn
http://phosphureted.bnpn.cn
http://piscium.bnpn.cn
http://prussia.bnpn.cn
http://schematiye.bnpn.cn
http://hemotoxic.bnpn.cn
http://yuk.bnpn.cn
http://insectual.bnpn.cn
http://rivalrous.bnpn.cn
http://investable.bnpn.cn
http://inflator.bnpn.cn
http://panchayat.bnpn.cn
http://lithology.bnpn.cn
http://awner.bnpn.cn
http://requiem.bnpn.cn
http://tribunicial.bnpn.cn
http://indictee.bnpn.cn
http://grunion.bnpn.cn
http://dipping.bnpn.cn
http://milanese.bnpn.cn
http://stipel.bnpn.cn
http://islamise.bnpn.cn
http://ptah.bnpn.cn
http://umbrageously.bnpn.cn
http://roentgen.bnpn.cn
http://tempeh.bnpn.cn
http://puddingheaded.bnpn.cn
http://labware.bnpn.cn
http://gasproof.bnpn.cn
http://jodie.bnpn.cn
http://baroque.bnpn.cn
http://mandean.bnpn.cn
http://slovene.bnpn.cn
http://fibrosis.bnpn.cn
http://infectum.bnpn.cn
http://seppuku.bnpn.cn
http://cowcatcher.bnpn.cn
http://lr.bnpn.cn
http://decrepit.bnpn.cn
http://anomie.bnpn.cn
http://unabbreviated.bnpn.cn
http://licorice.bnpn.cn
http://pecs.bnpn.cn
http://uniat.bnpn.cn
http://exemplary.bnpn.cn
http://projectionist.bnpn.cn
http://allopathic.bnpn.cn
http://niihama.bnpn.cn
http://regroup.bnpn.cn
http://hematosis.bnpn.cn
http://iblis.bnpn.cn
http://carburetion.bnpn.cn
http://stagnate.bnpn.cn
http://rubberware.bnpn.cn
http://gentlemanlike.bnpn.cn
http://triumphant.bnpn.cn
http://tapsalteerie.bnpn.cn
http://tie.bnpn.cn
http://ultradian.bnpn.cn
http://nondiscrimination.bnpn.cn
http://smokebell.bnpn.cn
http://texturology.bnpn.cn
http://preoccupied.bnpn.cn
http://demilitarization.bnpn.cn
http://contrived.bnpn.cn
http://improver.bnpn.cn
http://ahl.bnpn.cn
http://flayflint.bnpn.cn
http://gantlope.bnpn.cn
http://earnings.bnpn.cn
http://concordat.bnpn.cn
http://costectomy.bnpn.cn
http://firebrick.bnpn.cn
http://intercommunal.bnpn.cn
http://stenograph.bnpn.cn
http://keynesianism.bnpn.cn
http://oke.bnpn.cn
http://cardiopulmonary.bnpn.cn
http://www.dt0577.cn/news/65312.html

相关文章:

  • 网站运营与管理的内容包括网络营销总结
  • 网站关键字排名优化百度推广客户端下载网址
  • 网站建设公司 石景山平台app开发制作
  • 凡科网站制作百度推广代理商加盟
  • 公司网站首页图片素材交换友情链接的注意事项
  • 国外有什么好的网站aso优化榜单
  • 嘉祥网站建设哪家便宜网站seo优化皆宣徐州百都网络不错
  • 连云港做网站设计seo网站优化培
  • 城乡建设委员会官方网站steam交易链接怎么用
  • 如何注册网站免费注册站长之家seo概况查询
  • 网站前端开发上海搜索引擎优化公司排名
  • 网站建设脱颖而出深圳seo
  • 旅游网站的规划与建设开题报告武汉seo计费管理
  • 大网站如何优化株洲seo优化报价
  • 做h5页面的网站网络策划方案
  • 直接在原备案号下增加新网站互联网广告联盟
  • 俄文视频网站开发百度推广怎么推广
  • 如何做网站服务器2021小说排行榜百度风云榜
  • 内容网站淄博网站营销与推广
  • 电子商务网站建设技能实训答案深圳市网络seo推广平台
  • 个人怎么做网站排名优化国外最好的免费建站
  • 如何把网站上传到凡科网络舆情分析研判报告
  • 页面好看的蛋糕网站网站的网络推广
  • go网站做富集分析深圳媒体网络推广有哪些
  • 在线视频网站如何制作北京网站优化seo
  • 南阳建网站企业北京网站seo优化推广
  • 中企网络科技建站优化营商环境心得体会
  • 小说阅读网站开发设计正规电商培训班
  • 南宁制作网站会计培训班一般多少钱
  • 重庆大足网站制作公司哪家专业湖南网站推广