#34排序數(shù)組查首尾位置

medium，我寫的:1 暴力

vector<int> searchRange(vector<int>& nums, int target) {
        int start=-1;
        int end=-1;
        for(int i=0;i<nums.size();i++){
            if(nums[i]==target && start==-1) start=i;
            if(nums[i]==target && start>-1) end=i;
        }
        return {start,end};
    }

我寫的，做了個(gè)類似二分搜索的方法：

vector<int> searchRange(vector<int>& nums, int target) {
        
        int start=0;
        int end=nums.size()-1;
        int res=-1;

        while(start<=end){
            //cout<<"start: "<<start<<", end: "<<end<<endl;
            int mid=(start+end)/2;
            
            if(nums[mid]==target){
                res=mid;
                break;
            }

            if(target<nums[mid]) end=mid-1;
            if(target>nums[mid]) start=mid+1;
        }
        //cout<<res<<endl;
        start=res; end=res;
        while(start>=0 && nums[start]==target){
            start--;
        }
        while(end<nums.size() && nums[end]==target){
            end++;
        }
        
        //if(nums.size()==1) return {0,0};
        if(res==-1) return{-1,-1};
        return {start+1,end-1};
    }

隨想錄：從兩頭都做類似二分搜索

     vector<int> searchRange(vector<int>& 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};
    }
     int getRightBorder(vector<int>& nums, int target) {
        int left = 0;
        int right = nums.size() - 1;
        int rightBorder = -2; // 記錄一下rightBorder沒(méi)有被賦值的情況
        while (left <= right) {
            int middle = left + ((right - left) / 2);
            if (nums[middle] > target) {
                right = middle - 1;
            } else { // 尋找右邊界，nums[middle] == target的時(shí)候更新left
                left = middle + 1;
                rightBorder = left;
            }
        }
        return rightBorder;
    }
    int getLeftBorder(vector<int>& nums, int target) {
        int left = 0;
        int right = nums.size() - 1;
        int leftBorder = -2; // 記錄一下leftBorder沒(méi)有被賦值的情況
        while (left <= right) {
            int middle = left + ((right - left) / 2);
            if (nums[middle] >= target) { // 尋找左邊界
                right = middle - 1;
                leftBorder = right;
            } else {
                left = middle + 1;
            }
        }
        return leftBorder;
    }

#922?按奇偶排序數(shù)組II

我的解法，有點(diǎn)蠢：

vector<int> sortArrayByParityII(vector<int>& nums) {
        int cnt=0;
        vector<int> odd;
        vector<int> even;
        for(int i=0;i<nums.size();i++){
            if(i%2!=0 && nums[i]%2==0) odd.push_back(i);

            if (i%2==0 && nums[i]%2!=0) even.push_back(i);
        }

        for(int i=0;i<odd.size();i++){
            swap(nums[odd[i]],nums[even[i]]);
        }

        return nums;
        
    }

inplace解法： 把odd idx放的偶數(shù)，給換到even idx放的奇數(shù)

注意j是從1開(kāi)始，而且每輪i，j都是繼續(xù)增加不回去

空間表現(xiàn)很好，但時(shí)間表現(xiàn)很一般

vector<int> sortArrayByParityII(vector<int>& nums) {
        int j=1;
        for(int i=0;i<nums.size();i+=2){
            if(nums[i]%2){
                while(j<nums.size() && nums[j]%2) j+=2;
                swap(nums[i],nums[j]);
            }
        }
        return nums;
    }

#35搜索插入位置?

要求復(fù)雜度O log n ，我寫的：

int searchInsert(vector<int>& nums, int target) {
        int start=0;
        int end=nums.size()-1;
        while(start<=end){
            int mid=(start+end)/2;
            //cout<<"mid: "<<mid<<endl;
            if(nums[mid]==target) return mid;
            else if(mid==start) {
                if(start+1<nums.size() && target>nums[start+1]) return start+2;
                return target>nums[start]?start+1:start;
            }     
            if(nums[mid]>target) end=mid-1;
            if(nums[mid]<target) start=mid+1;
        }
        return -1;
    }

隨想錄寫的：所有情況都能統(tǒng)一變成return end+1或者return start

int searchInsert(vector<int>& nums, int target) {
        int start=0;
        int end=nums.size()-1;
        int mid;
        while(start<=end){
            mid=(start+end)/2;
            if(nums[mid]==target) return mid;
               
            if(nums[mid]>target) end=mid-1;
            if(nums[mid]<target) start=mid+1;
        }
        return end+1;
    }

這里沒(méi)想明白為什么不對(duì)，有空想想文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-609691.html

到了這里，關(guān)于代碼隨想錄額外題目| 數(shù)組03 ●34排序數(shù)組查首尾位置 ●922按奇偶排序數(shù)組II●35搜索插入位置的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！