【leetcode】二分法-34.在排序数组中查找元素的第一个和最后一个位置

【leetcode】二分法-34.在排序数组中查找元素的第一个和最后一个位置

题目：给定一个按照升序排列的整数数组 nums，和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。
如果数组中不存在目标值 target，返回 [-1, -1]。

题目分析：不考虑时间复杂度的话，可以直接遍历该列表，记录target所在的所有位置存放在一个vector中，如果遍历结束，该vector为空，则说明给定数组中没有target值；若该vector的size==1，则说明target只出现过一次，那么在补充填入一个结束位置即可；否则，该target在数组中出现多次，那么vector的长度可能大于2，仅需要提取第一个元素和末尾元素，即是target出现的开始位置和结束位置。

class Solution {
public:
    vector searchRange(vector& nums, int target) {
        vectorrange;
        vectorans;
        for(int i = 0;i 
执行用时：8 ms, 在所有 C++ 提交中击败了68.07%的用户
 内存消耗：13.4 MB, 在所有 C++ 提交中击败了18.60%的用户
 
进阶：
 可以设计并实现时间复杂度为 O(log n) 的算法解决此问题吗？
 
分析：O(log n)为二分法的复杂度，通过二分法，确定target的开始和结束位置。
 
class Solution {
public:
    vector searchRange(vector& nums, int target) {
        vectorrange;
        if(nums.size()!=0)
        {
            int a = 0,b = nums.size()-1;//用来记录开始的区间
            int c = 0,d = INT_MAX;//用来记录结束的区间
            bool no = false,no2= false;//标识是否遍历到过target
            int times=0;//表示第几次遍历到target，只有第一次才需要设置cd
            while(atarget)
                        {
                            c = c;
                            d = middle2-1;
                        }
                        else
                        {
                            c = middle2+1;
                            d = d;
                        }
                    }
                    else
                    {
                        c = middle2+1;
                        d = d;
                        //no2 = true;
                    }
                }
            }
            if(nums[a]==target && nums[c]==target)
            {
                range.push_back(a);
                range.push_back(c);
            }
            else if(nums[a]==target && nums[c]!=target)
            {
                range.push_back(a);
                if(no==false)
                {
                    range.push_back(a);
                }
                else
                {
                    range.push_back(c-1);
                }
            }
            else if(nums[a]!=target && nums[c]==target)
            {
                if(no==false)
                {
                    range.push_back(c);
                }
                else
                {
                    range.push_back(a+1);
                }
                range.push_back(c);
            }
            else
            {
                if(no==false)
                {
                    range.push_back(-1);
                    range.push_back(-1);
                }
                else
                {
                    range.push_back(a+1);
                    range.push_back(c-1); 
                }
            }
        }
        else
        {
            range.push_back(-1);
            range.push_back(-1);
        }
        return range;
    }
};
 
执行用时：0 ms, 在所有 C++ 提交中击败了100.00%的用户
 内存消耗：13.4 MB, 在所有 C++ 提交中击败了7.65%的用户
欢迎分享，转载请注明来源：内存溢出
原文地址:https://54852.com/zaji/4752335.html