LeetCode 面试题 10.05. 稀疏数组搜索

一、题目

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

示例1:

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

示例2:

输入： words = [“at”, “”, “”, “”, “ball”, “”, “”, “car”, “”, “”,“dad”, “”, “”], s = “ball”
输出： 4

提示:

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

  点击此处跳转题目。

二、C# 题解

  二分查找的变形，代码如下：

public class Solution {
    public int FindString(string[] words, string s) {
        return Partition(words, 0, words.Length, s);
    }

    public int Partition(string[] words, int i, int j, string target) {
        if (i >= j) return -1;
        
        int mid = (i + j) / 2;
        if (words[mid] == "") { // 该处为空，则左右均进行查找，这里优先查找左边
            int left = Partition(words, i, mid, target);
            if (left != -1) return left;
            return Partition(words, mid + 1, j, target);
        }
        
        if (words[mid] == target) return mid; // 找到则直接返回
        if (target.CompareTo(words[mid]) < 0) // 结果小，进入左枝
            return Partition(words, i, mid, target);
        return Partition(words, mid + 1, j, target); // 否则，进入右枝
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

• 时间：68 ms，击败 100.00% 使用 C# 的用户
• 内存：39.03 MB，击败 16.67% 使用 C# 的用户