Cinte's Leetcode Record
0%

面试题 10.05. 稀疏数组搜索

Posted on Edited on In Disqus:
Symbols count in article: 494 Reading time ≈ 1 mins.

面试题 10.05. 稀疏数组搜索

本质在于碰到""后缩减搜索区间

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 findString(vector<string>& words, string s) {
        int lo = 0, hi = words.size();
        while(lo <= hi)
        {
            int mid = lo + (hi - lo) / 2;
            if(words[lo] == "")
            {
                ++lo;
                continue;
            }
            if(words[hi] == "")
            {
                --hi;
                continue;
            }
            while(mid < hi && words[mid] == "")
                ++mid;
            if(words[mid] > s)
                hi = mid - 1;
            else if(words[mid] < s)
                lo = mid + 1;
            else
                return mid;
        }
        return -1;
    }
};