leetcode
leetcode 2801 ~ 2850
稀疏数组搜索

稀疏数组搜索

难度:

标签:

题目描述

Given a sorted array of strings that is interspersed with empty strings, write a method to find the location of a given string.

Example1:

 Input: words = ["at", "", "", "", "ball", "", "", "car", "", "","dad", "", ""], s = "ta"
 Output: -1
 Explanation: Return -1 if s is not in words.

Example2:

 Input: words = ["at", "", "", "", "ball", "", "", "car", "", "","dad", "", ""], s = "ball"
 Output: 4

Note:

  1. 1 <= words.length <= 1000000

代码结果

运行时间: 21 ms, 内存: 16.3 MB

/*
 * 稀疏数组搜索
 * 题目思路：
 * 使用Java Stream对数组进行处理，过滤掉空字符串，
 * 然后查找目标字符串的位置。
 */

import java.util.*;
import java.util.stream.*;

public class SparseArraySearchStream {
    public int findString(String[] words, String s) {
        List<String> wordList = Arrays.stream(words)
                                      .filter(word -> !word.isEmpty())
                                      .collect(Collectors.toList());
        return wordList.indexOf(s);
    }
}

解释

方法:

这个题解采用了一个二分查找的变体来处理含有空字符串的排序字符串数组。算法的核心是在常规的二分查找基础上加入了对空字符串的处理。在查找中值mid时，如果发现words[mid]是空字符串，则向右移动mid，直到找到非空字符串或者到达数组的右界。如果整个区间mid到right都是空字符串，那么调整搜索的右界限为mid左边的位置；如果找到了非空字符串，则比较这个字符串和目标字符串s。如果相等，则返回mid的位置；如果目标字符串小，则左移右界；反之，则右移左界。

时间复杂度:

O(n)

空间复杂度:

O(1)

代码细节讲解

🦆
在稀疏数组中进行二分查找时，为什么选择先向右移动mid以跳过空字符串，而不是选择向左移动？
▷
在稀疏数组中进行二分查找时，选择先向右移动mid以跳过空字符串而不是向左移动的原因主要是由于二分查找的初始mid位置是向左偏的（由于整数除法的特性）。因此，向右移动是为了更快地接近中间的非空字符串，尤其是在右半部分可能有更多连续的非空字符串的情况下。这种策略简化了逻辑，因为一旦向右移动找到非空字符串后，可以直接进行比较，而无需再回头处理左侧可能错过的非空字符串。
🦆
二分查找中，如果右侧全是空字符串导致调整右界至mid左边的位置，这种情况下如何保证不会错过目标字符串s的正确位置？
▷
在二分查找过程中，如果从mid向右移动直到数组末尾都是空字符串，将右界调整到mid左边的位置是安全的。这是因为，如果目标字符串s存在于数组中，它必然位于mid左侧的非空区域。此时缩小搜索范围到左侧，不会错过目标字符串s，因为右侧已经确认全为无效的空字符串，不可能包含目标字符串。
🦆
在数组两端存在大量空字符串的情况下，这种算法的效率如何影响，是否有更优的处理策略？
▷
在数组两端存在大量空字符串的情况下，这种基本的二分查找算法可能在效率上受到影响，因为需要额外的步骤来跳过这些空字符串，尤其是在边界情况下。一种可能的优化策略是在实施二分查找之前，先通过扫描来确定非空字符串的实际边界，然后在这个确定的区间内应用二分查找。这样可以减少中间过程中对空字符串的多次检测和跳过，从而提高算法的整体效率。

相关问题

无重复字符串的排列组合交换数字