Question

面试题 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]之间

解法

方法一

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

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;
  }
}

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;
  }
};

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
}