做网站设计前景怎么样,什么网站比较少人做,国外网站注册软件,常州建网站第一此次想到的解法是首先使用二分查找在排序数组中查找到一个指定元素#xff0c;随后对该元素左右进行遍历#xff0c;找到起始位置和结束位置#xff0c;代码如下#xff1a;
class Solution {
public:vectorint searchRange(vectorint nums, int…第一此次想到的解法是首先使用二分查找在排序数组中查找到一个指定元素随后对该元素左右进行遍历找到起始位置和结束位置代码如下
class Solution {
public:vectorint searchRange(vectorint nums, int target) {int size nums.size();int min 0;int max size - 1;while(min max){int mid min (max - min)/2;if(target nums[mid]){max mid - 1;}else if(target nums[mid]){min mid 1;}else{while(nums[min] ! target){min;}while(nums[max] ! target){max--;}return {min,max};}}return {-1,-1};}
};执行虽然通过但测试用时并不是很理想在 代码随想录 看到的解法是将题目分为三种情况
情况一target 在数组范围的右边或者左边例如数组{3, 4, 5}target为2或者数组{3, 4, 5},target为6此时应该返回{-1, -1}情况二target 在数组范围中且数组中不存在target例如数组{3,6,7},target为5此时应该返回{-1, -1}情况三target 在数组范围中且数组中存在target例如数组{3,6,7},target为6此时应该返回{1, 1}
采用二分法来分别寻找左边界和右边界最终分情况进行return。代码如下
class Solution {
public:vectorint searchRange(vectorint nums, int target) {int leftBorder getLeftBorder(nums, target);int rightBorder getRightBorder(nums, target);// 情况一if (leftBorder -2 || rightBorder -2) return {-1, -1};// 情况三if (rightBorder - leftBorder 1) return {leftBorder 1, rightBorder - 1};// 情况二return {-1, -1};}
private:int getRightBorder(vectorint nums, int target) {int left 0;int right nums.size() - 1;int rightBorder -2; // 记录一下rightBorder没有被赋值的情况while (left right) {int middle left ((right - left) / 2);if (nums[middle] target) {right middle - 1;} else { // 寻找右边界nums[middle] target的时候更新leftleft middle 1;rightBorder left;}}return rightBorder;}int getLeftBorder(vectorint nums, int target) {int left 0;int right nums.size() - 1;int leftBorder -2; // 记录一下leftBorder没有被赋值的情况while (left right) {int middle left ((right - left) / 2);if (nums[middle] target) { // 寻找左边界nums[middle] target的时候更新rightright middle - 1;leftBorder right;} else {left middle 1;}}return leftBorder;}
};将上述代码的两个二分查找函数进行合并
class Solution {
public:vectorint searchRange(vectorint nums, int target) {int leftBorder getBorder(nums, target, true);int rightBorder getBorder(nums, target, false);// 情况一if (leftBorder -2 || rightBorder -2) return {-1, -1};// 情况三if (rightBorder - leftBorder 1) return {leftBorder 1, rightBorder - 1};// 情况二return {-1, -1};}
private:int getBorder(vectorint nums, int target, bool flag) {int left 0;int right nums.size() - 1;int border -2;while (left right){int middle left (right - left)/2;if(flag) { //flag true返回左边界if (nums[middle] target) { // 寻找左边界nums[middle] target的时候更新rightright middle - 1;border right;} else {left middle 1;}}else{if (nums[middle] target) {right middle - 1;} else { // 寻找右边界nums[middle] target的时候更新leftleft middle 1;border left;}}}return border;}};
