Cinte's Leetcode Record
0%

剑指 Offer 53 - I. 在排序数组中查找数字 I

Posted on Edited on In Disqus:
Symbols count in article: 1.8k Reading time ≈ 2 mins.

剑指 Offer 53 - I. 在排序数组中查找数字 I

参考34. Find First and Last Position of Element in Sorted Array

直接遍历
1
2
3
4
5
6
7
8
9
class Solution {
public:
    int search(vector<int>& nums, int target) {
        int ret = 0;
        for(auto& num : nums)
            ret += num == target ? 1 : 0;
        return ret;
    }
};

O(n)

二分
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
27
28
29
class Solution {
public:
    int search(vector<int>& nums, int target) {
        if(nums.empty())
            return 0;
        int lo = 0, hi = nums.size(), mid;
        int ret = 0;
        while(lo < hi)
        {
            mid = lo + ((hi - lo) >> 1);
            if(nums[mid] == target)
            {
                ++ret;
                break;
            }
            else if(nums[mid] > target)
                hi = mid - 1;
            else
                lo = mid + 1;
        }
        int i = mid - 1;
        while(i >= 0 && nums[i--] == target)
            ++ret;
        i = mid + 1;
        while(i <= nums.size() - 1 && nums[i++] == target)
            ++ret;
        return ret;
    }
};

优化 

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
27
28
29
30
class Solution {
public:
    int search(vector<int>& nums, int target) {
        if(nums.empty())
            return 0;
        int lo = 0, hi = nums.size() - 1;
        while(lo < hi)
        {
            int mid = (lo + hi) >> 1;
            if(nums[mid] < target)
                lo = mid + 1;
            else
                hi = mid;
        }
        int left = hi; // 最后保留一个等于目标的左边界
        if(nums[lo] != target)
            return 0;
        hi = nums.size() - 1;
        while(lo < hi)
        {
            int mid = ((lo + hi) >> 1) + 1; // 偏向右边
            if(nums[mid] <= target)
                lo = mid;
            else
                hi = mid - 1;
        }
        // 保留一个等于左边的左边界
        return lo - left + 1;
    }
};
v.2 
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
27
28
29
30
31
class Solution {
public:
    int search(vector<int>& nums, int target) {
        if(nums.empty())
            return 0;
        int lo = 0, hi = nums.size() - 1;
        while(lo <= hi)
        {
            int mid = (lo + hi) >> 1;
            if(nums[mid] < target)
                lo = mid + 1;
            else
                hi = mid - 1;
        }
        // 当他们相等时候，进入会出现hi在lo的前面一位，即hi是左边界而lo是左边界右边一个，hi!=target而lo==target
        int left = hi;
        if(lo <= nums.size() - 1 && nums[lo] != target) // lo如果不等于的话，那就直接跳出
            return 0;
        hi = nums.size() - 1;
        while(lo <= hi)
        {
            int mid = (lo + hi) >> 1;
            if(nums[mid] <= target)
                lo = mid + 1;
            else
                hi = mid - 1;
        }
        // lo是右边界
        return lo - left - 1;
    }
};