判断字符数组中是否所有的字符都只出现过一次 & 在有序但含有空的数组中查找字符串

判断字符数组中是否所有的字符都只出现过一次

题目：判断数组中所有的数字是否只出现一次

《程序员代码面试指南》第81题 P261 难度：要求1:士★☆☆☆ 要求2:尉★★☆☆

要求1很简单，时间复杂度为O(N)，遍历一遍chas，用map记录每种字符的出现情况即可。书中使用了长度固定的数组，也可以使用哈希表来实现。

public boolean isUnique1(char[] chas) {
    if (chas == null) {
        return true;
    }
    boolean[] map = new boolean[256];
    for (int i = 0; i < chas.length; i++) {
        if (map[chas[i]]) {
            return false;
        }
        map[chas[i]] = true;
    }
    return true;
}

要求2的整体思路是先将chas排序，排序后相同的字符就放在一起。所以问题的关键是选择什么样的排序算法，使得额外空间复杂度为O(1)，并且时间复杂度尽量低。

public boolean isUnique2(char[] chas) {
    if (chas == null) {
        return true;
    }
    heapSort(chas);
    for (int i = 1; i < chas.length; i++) {
        if (chas[i] == chas[i - 1]) {
            return false;
        }
    }
    return true;
}

public void heapSort(char[] chas) {
    for (int i = 0; i < chas.length; i++) {
        heapInsert(chas, i);
    }
    for (int i = chas.length - 1; i > 0; i--) {
        swap(chas, 0, i);
        heapify(chas, 0, i);
    }
}

public void heapInsert(char[] chas, int i) {
    int parent = 0;
    while (i != 0) {
        parent = (i - 1) / 2;
        if (chas[parent] < chas[i]) {
            swap(chas, parent, i);
            i = parent;
        } else {
            break;
        }
    }
}

public void heapify(char[] chas, int i, int size) {
    int left = i * 2 + 1;
    int right = i * 2 + 2;
    int largest = i;
    while (left < size) {
        if (chas[left] > chas[i]) {
            largest = left;
        }
        if (right < size && chas[right] > chas[largest]) {
            largest = right;
        }
        if (largest != i) {
            swap(chas, largest, i);
        } else {
            break;
        }
        i = largest;
        left = i * 2 + 1;
        right = i * 2 + 2;
    }
}

public void swap(char[] chas, int index1, int index2) {
    char tmp = chas[index1];
    chas[index1] = chas[index2];
    chas[index2] = tmp;
}

在有序但含有空的数组中查找字符串

题目：在有序但是含有空的数组中查找字符串

《程序员代码面试指南》第82题 P263 难度：尉★★☆☆

【解答】
本题的解法尽可能多地使用了二分查找，具体过程如下：

1. 假设在strs[left..right]上进行查找的过程，全局整型变量res表示字符串str在strs中最左的位置。初始时，left=0，right=strs.length-1, res=-1。
2. 令mid=(left+right)/2，则strs[mid]为strs[left..right]中间位置的字符串。
3. 如果字符串strs[mid]与str一样，说明找到了str，令res=mid。但要找的是最左的位置，还要在左半区寻找，看有没有更左的str出现，所以令right=mid-1，然后重复步骤2。
4. 如果字符串strs[mid]与str不一样，并且strs[mid]!=null，此时可以比较strs[mid]和str，如果strs[mid]的字典顺序比str小，说明整个左半区不会出现str，需要在右半区寻找，所以令left=mid+1，然后重复步骤2。
5. 如果字符串strs[mid]与str不一样，并且strs[mid]==null，此时从mid开始，从右到左遍历左半区（即strs[left..mid]）。如果整个左半区都为null，那么继续用二分的方式在右半区上查找（即令left=mid+1），然后重复步骤2。如果整个左半区不都为null，假设从右到左遍历strs[left..mid]时，发现第一个不为null的位置是i，那么把str和strs[i]进行比较。如果strs[i]字典顺序小于str，同样说明整个左半区没有str，令left=mid+1，然后重复步骤2。如果strs[i]字典顺序等于str，说明找到str，令res=mid，但要找的是最左的位置，还要在strs[left..i-1]上寻找，看有没有更左的str出现，所以令right=i-1，然后重复步骤2。如果strs[i]字典顺序大于str，说明strs[i..right]上都没有str，需要在strs[left..i-1]上查找，所以令right=i-1，然后重复步骤2。

具体过程请参看如下代码中的getlndex方法。

public int getIndex(String[] strs, String str) {
    if (strs == null || strs.length == 0 || str == null) {
        return -1;
    }
    int res = -1;
    int left = 0;
    int right = strs.length - 1;
    int mid = 0;
    int i = 0;
    while (left <= right) {
        mid = (left + right) / 2;
        if (strs[mid] != null && strs[mid].equals(str)) {
            res = mid;
            right = mid - 1;
        } else if (strs[mid] != null) {
            if (strs[mid].compareTo(str) < 0) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        } else {
            i = mid;
            while (strs[i] == null && --i >= left)
                ;
            if (i < left || strs[i].compareTo(str) < 0) {
                left = mid + 1;
            } else {
                res = strs[i].equals(str) ? i : res;
                right = i - 1;
            }
        }
    }
    return res;
}