「每日LeetCode」2021年4月4日

本文最后更新于：2023年3月19日 晚上

面试题 10.05. 稀疏数组搜索

面试题 10.05. 稀疏数组搜索

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

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

示例 2:

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

提示:

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

思路

因为数组是有序的，使用二分查找，每次循环内求中求中点，然后用一个 temp 记录这个中点，向左边开始线性查找第一个非空元素，查到以后和 s 进行比较，如果相等返回该下标，如果比 s 大，说明要找的元素在 left 到当前元素中间。如果比 s 小，说明这个值在临时记录的 temp 到 right 之间。

解答

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
/**
 * @param {string[]} words
 * @param {string} s
 * @return {number}
 */
var findString = function (words, s) {
  let left = 0,
    right = words.length - 1;
  while (left <= right) {
    let middle = Math.ceil((left + right) / 2);
    const temp = middle;
    while (!words[middle] && middle > left) {
      middle--;
    }

    if (words[middle] === s) return middle;
    else if (words[middle] > s) {
      right = middle - 1;
    } else {
      left = temp + 1;
    }
  }
  return -1;
};