字符串问题——在有序但有空的数组中查找字符串

Posted on | In ,

题目：给定一个数组strs[]，strs中的某些位置是null，但在不为null的位置上，字符串是按照字典顺序由小到大一次出现的。再给定一个字符串str，返回str在strs中最左边的位置。
例：
strs=[null, “a”, null, “a”, null, “b”, null, “c”],
str=”a”,返回1；
str=null,只要str为null，返回-1；
str=”d”，不存在则返回-1。
实现：利用二分法查找

  1. 定义全局整型变量rst，表示str在strs中最左边的位置。初始化，left=0，right=strs.length-1，rst=-1。
  2. 令mid=(left+right)/2，若strs[mid]==str，说明找到了str，rst=mid，但不确定是否是最左边的str，因此right=mid-1。重复步骤2。
  3. 如果strs[mid]!=str，并且str[mid]!=null，比较strs[mid]与str的大小，若str比strs[mid]小，则right=mid-1；否则left=mid+1。然后重复步骤2。
  4. 如果strs[mid]!=str，并且str[mid]==null，通过while控制向左移动，左边没有元素或找到的字典顺序小于str，则letf = mid+1；字典顺序大或等于str，rst=strs[i].equals(str) ? i : rst，right=i-1.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
public class GetIndex {
	public static int getIndex(String[] strs, String str) {
		if (strs == null || strs.length == 0 || str == null) {
			return -1;
		}
		int left = 0;
		int right = strs.length - 1;
		int rst = -1;
		int i = 0;
		while (left <= right) {
			int mid = (left + right) / 2;
			if (strs[mid] == str) {
				rst = mid;
				right = mid - 1;
			} else if (strs[mid] != null) { //strs[mid] != str && strs[mid] != null
				if (strs[mid].compareTo(str) < 0) { // 如果中间数比str小，说明str可能在右半区
					left = mid + 1;
				} else { // 否则在左半区
					right = mid - 1;
				}
			} else { //strs[mid] != str && strs[mid] == null
				i = mid;
				while (strs[i] == null && --i >= left); //左边没有元素（都为null）
				if (i < left || strs[i].compareTo(str) < 0) { //或找到的字段顺序小于str
					left = mid + 1;
				} else { //strs[i]字典顺序大于或等于str
					rst = strs[i].equals(str) ? i : rst;
					right = i - 1;
				}
			}
		}
		return rst;
	}
	//Test
	public static void main(String[] args) {
		String[] strs = {null, "a", null, "a", null, "b", null, "c"};
		String str = "a";
		System.out.println(getIndex(strs, str));
	}
}