可乐的博客
0%

leetcode 35 Search Insert Position

发表于 更新于
本文字数： 1.2k 阅读时长 ≈ 1 分钟

给出一个数组，给定一个数字，查找需要插入的位置，数组已排好序，瞬间想到二分搜索，然后判断位置就可以了，判断位置判断的有点失败.....

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    int searchInsert(vector<int>& nums, int target) {
        int left=0,right=nums.size(),middle=0;
        int flag=0;
        while(left<=right)
        {
            middle=(left+right)/2;
            if(nums[middle]==target)
                {flag=1;break;}
            if(nums[middle]>target) right=middle-1;
            else left=middle+1;
        }
        //return middle;
        if(flag==1) return middle;
        else
        {
            if(nums[middle]<target) return middle+1>nums.size()?nums.size():middle+1;
            else if(nums[middle]>target) return middle;
        }
    }
};

修改版 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
public:
    int searchInsert(vector<int>& nums, int target) {
        int left=0,right=nums.size()-1,middle=0;
        int flag=0;
        while(left<right)
        {
            middle=(left+right)/2;
            if(nums[middle]==target)
                return middle;
            if(nums[middle]>target) right=middle-1;
            else left=middle+1;
        }
        //return middle;
        /*
        if(flag==1) return middle;
        else
        {
            if(nums[middle]<target) return middle+1>nums.size()?nums.size():middle+1;
            else if(nums[middle]>target) return middle;
        }*/
        if(nums[left]==target||nums[left]>target) return left;
        else
            return left+1;
    }
};
运行时间多了2ms,但玄学的问题无法解决的....