面试题 10.05. 稀疏数组搜索

Posted on | In
Words count in article: 232 | Reading time ≈ 1

题目

稀疏数组搜索。有个排好序的字符串数组，其中散布着一些空字符串，编写一种方法，找出给定字符串的位置。

示例1：

1
2
3
输入: words = ["at", "", "", "", "ball", "", "", "car", "", "","dad", "", ""], s = "ta"
 输出：-1
 说明: 不存在返回-1。

示例2：

1
2
输入：words = ["at", "", "", "", "ball", "", "", "car", "", "","dad", "", ""], s = "ball"
 输出：4

提示：

  • words的长度在[1, 1000000]之间

解法

解法一：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public int findString(String[] words, String s) {
        int begin = 0;
        int end = words.length - 1;
        while (begin <= end) {
            int mid = (begin + end) / 2;
            while (begin < mid && "".equals(words[mid])) {
                mid--;
            }
            if (words[mid].compareTo(s) > 0) {
                end = mid - 1;
            } else if (words[mid].compareTo(s) < 0) {
                begin = mid + 1;
            } else {
                return mid;
            }
        }
        return -1;
    }
0%