README.md

面试题 10.05. 稀疏数组搜索

中文文档

题目描述

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

示例1:

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

示例2:

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

提示:

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

解法

Python3

class Solution:
    def findString(self, words: List[str], s: str) -> int:
        left, right = 0, len(words) - 1
        while left < right:
            mid = (left + right) >> 1
            while left < mid and words[mid] == '':
                mid -= 1
            if s <= words[mid]:
                right = mid
            else:
                left = mid + 1
        return -1 if words[left] != s else left

Java

class Solution {
    public int findString(String[] words, String s) {
        int left = 0, right = words.length - 1;
        while (left < right) {
            int mid = (left + right) >> 1;
            while (left < mid && "".equals(words[mid])) {
                --mid;
            }
            if (s.compareTo(words[mid]) <= 0) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        return s.equals(words[left]) ? left : -1;
    }
}

C++

class Solution {
public:
    int findString(vector<string>& words, string s) {
        int left = 0, right = words.size() - 1;
        while (left < right) {
            int mid = left + right >> 1;
            while (left < mid && words[mid] == "") --mid;
            if (s <= words[mid])
                right = mid;
            else
                left = mid + 1;
        }
        return words[left] == s ? left : -1;
    }
};

Go

func findString(words []string, s string) int {
	left, right := 0, len(words)-1
	for left < right {
		mid := (left + right) >> 1
		for left < mid && words[mid] == "" {
			mid--
		}
		if s <= words[mid] {
			right = mid
		} else {
			left = mid + 1
		}
	}
	if words[left] == s {
		return left
	}
	return -1
}

...