本文小编为大家详细介绍“怎么用C++在有序数组中查找元素的第一个和最后一个位置”，内容详细，步骤清晰，细节处理妥当，希望这篇“怎么用C++在有序数组中查找元素的第一个和最后一个位置”文章能帮助大家解决疑惑，下面跟着小编的思路慢慢深入，一起来学习新知识吧。Given an array of integersnumssorted in ascending order, find the starting and ending position of a giventargetvalue.Your algorithm”s runtime complexity must be in the order ofO(logn).If the target is not found in the array, return[-1, -1].Example 1:Input: nums = [5,7,7,8,8,10], target = 8
Output: [3,4]Example 2:Input: nums = [5,7,7,8,8,10], target = 6
Output: [-1,-1]这道题让我们在一个有序整数数组中寻找相同目标值的起始和结束位置，而且限定了时间复杂度为 O(logn)，这是典型的二分查找法的时间复杂度，所以这里也需要用此方法，思路是首先对原数组使用二分查找法，找出其中一个目标值的位置，然后向两边搜索找出起始和结束的位置，代码如下：解法一:可能有些人会觉得上面的算法不是严格意义上的 O(logn) 的算法，因为在最坏的情况下会变成 O(n)，比如当数组里的数全是目标值的话，从中间向两边找边界就会一直遍历完整个数组，那么下面来看一免费云主机域名种真正意义上的 O(logn) 的算法，使用两次二分查找法，第一次找到左边界，第二次调用找到右边界即可，具体代码如下：解法二：其实我们也可以只使用一个二分查找的子函数，来同时查找出第一个和最后一个位置。如何只用查找第一个大于等于目标值的二分函数来查找整个范围呢，这里用到了一个小 trick，首先来查找起始位置的 target，就是在数组中查找第一个大于等于 target 的位置，当返回的位置越界，或者该位置上的值不等于 target 时，表示数组中没有 target，直接返回 {-1, -1} 即可。若查找到了 target 值，则再查找第一个大于等于 target+1 的位置，然后把返回的位置减1，就是 target 的最后一个位置，即便是返回的值越界了，减1后也不会越界，这样就实现了使用一个二分查找函数来解题啦，参见代码如下：解法三：读到这里，这篇“怎么用C++在有序数组中查找元素的第一个和最后一个位置”文章已经介绍完毕，想要掌握这篇文章的知识点还需要大家自己动手实践使用过才能领会，如果想了解更多相关内容的文章，欢迎关注百云主机行业资讯频道。
本篇内容介绍了“如何使用@Secured注解限制方法调用”的有关知识，在实际案例的操作过程中，不少人都会遇到这样的困境，接下来就让小编带领大家学习一下如何处理这些情况吧！希望大家仔细阅读，能够学有所成！在Spring Securoty实现方法级别的安全性最常见…
免责声明：本站发布的图片视频文字，以转载和分享为主，文章观点不代表本站立场，本站不承担相关法律责任；如果涉及侵权请联系邮箱：360163164@qq.com举报，并提供相关证据，经查实将立刻删除涉嫌侵权内容。
微信扫一扫 
