程序员面试金典 - CM1 确定字符互异

确定字符互异

http://www.nowcoder.com/questionTerminal/9618c2a9e8a14c3e82954ee14168f592

题目中要求不能使用额外的存储结构，因此会限制很多空间上的用法。首先想到的就是在时间上的暴力法。
针对每一个字符，我们都可以做到从当前字符的下一个位置来进行判断是否与当前字符相同，如果相同则返回 false，重复上面步骤，直到判断完所有字符没有相同的，就返回 true。

a  e  i  o  u
↑  → 判断每一个是否与当前字符相同
a  e  i  o  u
   ↑  → 判断每一个是否与当前字符相同
...

    public boolean checkDifferent(String iniString) {
        // write code here
        // 暴力法
        if(iniString == null || iniString.length() == 0)
            return false;
        for (int i = 0; i < iniString.length(); i++) {
            // 每一个位置都从当前位置的下一个位置进行判断 因为前面的已经判断过 不许重复判断
            for (int j = i+1; j < iniString.length(); j++) {
                if(iniString.charAt(i) == iniString.charAt(j))
                    return false;
            }
        }
        return true;
    }

分析：时间复杂度由于嵌套了两层循环 $图片说明$
空间复杂度 O(1).

如果将 String 字符串换成char[] 数组，这样就可以使用很多优化的方法。这里自己进行了一些拓展，并不符合本题要求，仅供参考。

注意：使用 char 数组来处理，就又可以提出多种解法。

第一种使用堆排序，使用大根堆小根堆都可以，思路如下，

思路：构建堆之后，在进行堆排序的过程中可以进行判断相邻的两个字符是否相等，如果相等： chars[j] == chars[j+1]就返回 false，如果完成排序就说明没有相同的字符，就可以返回 true。

以 a e i o u a 为例子

图片说明

代码

public boolean heapSortWithChars(char[] chars){
        if(chars == null || chars.length == 0)
            return false;
        // 构建堆
        int length = chars.length;
        for(int i = length/2-1; i >= 0; i--){
            buildHeap(chars, i, length);
        }
        // 排序
        for (int j = length-1; j >= 0 ; j--) {
            char temp = chars[j];
            chars[j] = chars[0];
            chars[0] = temp;
            // 进行判断
            if(j < length-1 && chars[j] == chars[j+1]){
                return false;
            }
            buildHeap(chars, 0, j);
        }
        return true;
    }

    public void buildHeap(char[] chars, int i, int length){
        char temp = chars[i];  // 先暂存当前元素
//        System.out.println("chars["+i+"] :"+chars[i]);
        for(int k = 2*i+1; k < length; k=2*k+1){
            // 先判断 左右谁大
            if(k+1 < length && chars[k] < chars[k+1]){
                k++;
            }
            if(chars[k] > temp){
                chars[i] = chars[k];
                i = k;
            }else {
                break;
            }
        }
        chars[i] = temp;
    }

分析：时间复杂度 O(nlogn) 堆排序、空间复杂度 O(n) 使用了char数组。

第二种就是使用寻找最长非重复子串的方法来进行处理

思路：如果最后得到的非重复最长子串长度等于源字符串长度那么就说明没有重复的字符，就返回 true，否则就返回 false。另外，在判断的过程中其实不一定要等到遍历完整个字符串才能判断，如果中间有重复子串，可以提前进行判断。
可以定义 pre 指向非重复子串的前一个位置，比如 aabc 那么 pre 就指向第一个 a ，即pre = 0 (初始为-1)。
开辟一个 256 数组map，其中map[i] 表示 i 最近出现的位置，初始化为 -1。

代码

// 使用 不重复的最长字符串
    public boolean checkDifferent3(String s){
        if(s == null || s.length() == 0)
            return false;

        char[] chars = s.toCharArray();
        int[] map = new int[256];
        // map[i] 表示 i 最近出现的位置
        for (int i = 0; i < 256; i++) {
            map[i] = -1;
        }
        // pre 指向 非重复串的前一个位置   比如 aabc pre 指向第一个 a
        int pre = -1;
        int len = 0;

        for (int i = 0; i < chars.length; i++) {
            // 取pre 或者map[chars[i]] 作为最新的起始点
            pre = Math.max(pre, map[chars[i]]);
            // 获取 当前长度值
            int curLen = i - pre;
            // 查看是否是最长的长度值
            len = Math.max(len, curLen);
            map[chars[i]] = i;
            // 提前判断 重复情况 "剪枝"
            if(pre != -1)
                return false;
        }
        return true;
    }

分析：时间复杂度 O(n), 空间复杂度 O(n)
其中非重复子串部分思想，参考了左程云的《程序员代码面试指南》。
以上为个人的理解，如有错误，欢迎指正和讨论。