LeetCode刷题-稀疏数组搜索

前言说明

算法学习，日常刷题记录。

题目连接

稀疏数组搜索

题目内容

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

示例1:

输入: words = ["at", "", "", "", "ball", "", "", "car", "", "","dad", "", ""], s = "ta"

输出：-1

说明: 不存在返回-1。

示例2:

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

输出：4

说明:

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

分析过程

因为字符串数组是有序的，使用二分查找法来解决。

字符串比较大小通过字符串的compareTo方法来实现，compareTo方法传递的参数就是要比较的字符串。

当结果小于0时，当前字符串比参数中的字符串小。

当结果等于0时，当前字符串等于参数中的字符串。

当结果大于0时，当前字符串比参数中的字符串大。

但是这里有空字符串，当二分查找遇到空字符串时，无法判断下一步，这里需要对二分查找进行调整，如下：

遇到空字符串，中间指针往左移动，直到不为空字符串或者大于左指针，结束循环；或者中间指针往右移动，直到不为空字符串或者小于右指针，结束循环。

第一步

定义中间指针center。

定义左指针left，初始为0。

定义右指针right，初始为字符串数组words的最后下标。

第二步

开始二分查找，进行while循环，直到左指针left大于右指针right，结束while循环。

第三步

每次while循环时：

1、计算中间指针center，中间指针center = (左指针left + 右指针right) / 2，除以2可以用位运算>>1来代替。

2、当二分查找遇到了特殊值导致无法继续时，就临时退化为线性遍历。这里存在空字符串，当遇到空字符串时，中间指针center向左移动，直到不为空字符串或者大于左指针left，结束循环。

3、开始判断给定字符串s符合哪种情况：

若给定字符串s等于字符串数组words中间指针center的元素，那么找到了目标值，返回中间指针center，结束程序。

若给定字符串s小于字符串数组words中间指针center的元素，那么目标值落在字符串数组words的前半部分，把右指针right更新为中间指针center减1，继续while循环，直到左指针left大于右指针right，结束while循环，结束程序。

若给定字符串s大于字符串数组words中间指针center的元素，那么目标值落在字符串数组words的后半部分，把左指针left更新为中间指针center加1，继续while循环，直到左指针left大于右指针right，结束while循环，结束程序。

第四步

若结束while循环也没有找到给定字符串s，那么返回-1，结束程序。

解答代码

class Solution {
    public int findString(String[] words, String s) {
        // 因为字符串数组是有序的，可以通过修改二分查找法来解决
        // 遇到空字符串，中间指针往左移动，直到不为空字符串或者大于左指针，结束循环；或者中间指针往右移动，直到不为空字符串或者小于右指针，结束循环

        // 定义中间指针
        int center;
        // 定义左指针
        int left = 0;
        // 定义右指针
        int right = words.length - 1;

        // 二分查找，进行循环，直到左指针大于右指针，结束循环
        while (left <= right) {
            // 计算获取中间指针，可以用位运算向右移动1位来代替除以2
            center = (left + right) >> 1;

            // 当遇到了特殊值导致正常的二分无法继续时，就临时退化为线性遍历
            // 当遇到空字符串，中间指针向左移动，直到不为空字符串或者大于左指针，结束循环(这里和二分查找法不同，其他地方一模一样)
            while (center > left && "".equals(words[center])) {
                --center;
            }

            if (s.equals(words[center])) {
                // 若给定字符串等于字符串数组中间指针的元素，那么找到了目标值，返回中间指针
                return center;
            } else if (s.compareTo(words[center]) < 0) {
                // 字符串的compareTo()方法用于两个字符串的比较，按字典顺序比较两个字符串
                // 若给定字符串小于字符串数组中间指针的元素，那么目标值落在字符串数组的前半部分，把右指针更新为中间指针减1
                right = center - 1;
            } else {
                // 若给定字符串大于字符串数组中间指针的元素，那么目标值落在字符串数组的后半部分，把左指针更新为中间指针加1
                left = center +1;
            }
        }

        // 若没有找到给定字符串，返回-1
        return -1;
    }
}

提交结果

执行用时0ms，时间击败100.00%的用户，内存消耗38.1MB，空间击败90.86%的用户。

运行结果

原文链接

原文链接：稀疏数组搜索