LeetCode 稀疏数组搜索/搜索插入位置-一一网

这是我参与更文挑战的第 13 天，活动详情查看：更文挑战

稀疏数组搜索（面试题10.05）

题目描述

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

示例 1：

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

示例 2：

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

提示

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

思路分析

稀疏数组的搜索，因为除了空字符串，已经是排好序的数组，所以我们也可以使用二分法进行查找，每次遇到是空字符串时，使用两个指针，分别左右进行探测，直到探测到非空字符串，我们可以使用双指针进行探测，但是也可以使用其他解法，比如我们可以对 low 自加，然后下个循环计算 mid 时重新定位，直到遇到非空字符串。本道题使用双指针解法。

二分查找有一定的套路，首先定义 low 和 high，while 循环的判断条件一直是 low <= high，对于 low == high，必要的时候特殊处理，在 while 内部补充，返回值永远是 mid；low、high 的更新永远是 low = mid + 1 和 high = mid – 1；

对于非确定性的查找，使用前后探测法，来确定搜索区间。先处理命中情况，再处理左右半部分查找的情况。

代码展示

解法一：时间复杂度是 ${O(logn)}$ ，空间复杂度是 ${O(1)}$ 。

public int findString(String[] words, String s) {
        int low = 0;
        int high = words.length - 1;
        while (low <= high){
            // 输入：words = ["at", "", "", "", "ball", "", "", "car", "", "","dad", "", ""], s = "ball"

            int mid = low + (high - low)/2;
            if (words[mid].isEmpty()) {  //只对口你那个空字符串这么处理
                int left = mid - 1;
                int right = mid + 1;
                while (true) {
                    if (left < low && right > high) {
                        return -1;
                    } else if (left >= low && !words[left].isEmpty()) {
                        mid = left;
                        break;
                    } else if (right <= high && !words[right].isEmpty()) {
                        mid = right;
                        break;
                    }
                    left--;
                    right++;
                }
            }

            if (s.compareTo(words[mid]) == 0){
                return mid;
            } else if(s.compareTo(words[mid]) > 0){
                low = mid + 1;
            } else {
                high = mid - 1;
            }

        }
        return -1;

    }
复制代码

搜索插入位置（35）

题目描述

给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。

你可以假设数组中无重复元素。

示例 1：

输入: [1,3,5,6], 5
输出: 2
复制代码

示例 2：

输入: [1,3,5,6], 2
输出: 1
复制代码

示例 3：

输入: [1,3,5,6], 7
输出: 4
复制代码

示例 4：

输入: [1,3,5,6], 0
输出: 0
复制代码

思路分析

搜索插入位置，如果找到目标值，就返回目标值的索引，如果没有找到目标值，那么就插入指定的位置，我们可以用二分法不断的逼近指定的目标值，最终返回目标值。

对于非确定性的查找，使用前后探测法，来确定搜索区间。先处理命中情况，再处理左右半部分查找的情况。

代码展示

解法一：时间复杂度是 ${O(logn)}$ ，空间复杂度是 ${O(1)}$ 。

public int searchInsert(int[] nums, int target) {
        int n = nums.length;
        int left = 0, right = n - 1, ans = n;
        while (left <= right) {
            int mid = ((right - left) >> 1) + left;
            if (target <= nums[mid]) {
                ans = mid;
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return ans;
    }
复制代码