中山做app网站公司吗,洛阳网站建设公司,品牌推广策略分析,网站名字怎么取最好题目链接
稀疏数组搜索
题目描述 注意点
字符串数组中散布着一些空字符串words的长度在[1, 1000000]之间字符串数组是排好序的数组中的字符串不重复
解答思路
因为数组中的字符串是排好序的#xff0c;所以首先想到的是二分查找#xff0c;先将数组中长度与s相同的字符串…题目链接
稀疏数组搜索
题目描述 注意点
字符串数组中散布着一些空字符串words的长度在[1, 1000000]之间字符串数组是排好序的数组中的字符串不重复
解答思路
因为数组中的字符串是排好序的所以首先想到的是二分查找先将数组中长度与s相同的字符串统计出来然后二分比较字符串word与s如果word小于s则向右二分如果word大于s则向左二分
代码
class Solution {public int findString(String[] words, String s) {ListInteger list new ArrayList();for (int i 0; i words.length; i) {if (words[i].length() s.length()) {list.add(i);}}int left 0;int right list.size() - 1;while (left right) {int mid left ((right - left) 1);int idx list.get(mid);int res words[idx].compareTo(s);if (res 0) {return idx;}if (res 0) {left mid 1;} else {right mid - 1;}}return -1;}
}关键点
二分查找的思想
