---

套路

• 关键字：（不）重复、复制、第一个、只出现一次
• 寻找只出现一次的答案是可以用到哈希表
• LinkedHashMap是有序的hashMap，可以找到第一个出现一次的字符

---

注意点

• 遍历map时 Map.Entry<> en : map.entrySet()

---

目录

• 数组中重复的数字
• 复杂链表的复制
• 字符流中第一个不重复的字符
• 数组中只出现一次的数字
• 第一个只出现一次的字符

---

数组中重复的数字

在一个长度为n的数组里的所有数字都在0到n-1的范围内。 数组中某些数字是重复的，但不知道有几个数字是重复的。也不知道每个数字重复几次。请找出数组中任意一个重复的数字。 例如，如果输入长度为7的数组{2,3,1,0,2,5,3}，那么对应的输出是第一个重复的数字2。

• 常规解法：数组中所有数字的值与哈希表下标索引建立关联，出现数组变为1，重复出现（即发现该位置为1），则返回该索引。时间复杂度为 N，空间复杂度为 N
• 最优解法：利用题目中所说在一个长度为n的数组里的所有数字都在0到n-1的范围内，这个数组自身就是一个完美的哈希表。让数组中每个元素不仅包含元素自身，还能够代表当前索引对应的数是否重复即可。时间复杂度为 N，空间复杂度为 O(1)相当于是一个加密解密的过程，一个位置包含两种含义

public boolean duplicate(int numbers[],int length,int [] duplication) {
    if (numbers == null || length == 0) {
        return false;
    }
    for (int i = 0; i < length; i++) {
        int val = numbers[i] % length;
        if (numbers[val] < length) {
            numbers[val] += length;
        } else {
            duplication[0] = val;
            return true;
        }
    }
    return false;
}

---

复杂链表的复制

输入一个复杂链表（每个节点中有节点值，以及两个指针，一个指向下一个节点，另一个特殊指针指向任意一个节点），返回结果为复制后复杂链表的head。（注意，输出结果中请不要返回参数中的节点引用，否则判题程序会直接返回空）

• 最优解：哈希表(hashmap)存放原节点和复杂链表对应新节点的双向key-value值，第一遍遍历填充新链表节点的值和next指针，第二遍遍历填充新链表节点的random指针。

public class RandomListNode {
    int label;
    RandomListNode next = null;
    RandomListNode random = null;
    RandomListNode(int label) {
        this.label = label;
    }
}

public RandomListNode Clone(RandomListNode pHead) {
    Map<RandomListNode, RandomListNode> map = new HashMap<>();
    // 创建复制链表的额外头结点，方便复制链表所有节点操作的统一处理
    RandomListNode cloneFront = new RandomListNode(0);
    RandomListNode p1 = pHead, p2 = cloneFront;
    while (p1 != null) {
        p2.next = new RandomListNode(p1.label);
        // 哈希表存放原节点和复制节点的双向键值对
        map.put(p2.next, p1);
        map.put(p1, p2.next);
        p2 = p2.next;
        p1 = p1.next;
    }
    p2 = cloneFront.next;
    while (p2 != null) {
        p2.random = map.get(map.get(p2).random);
        p2 = p2.next;
    }
    return cloneFront.next;
}

---

字符流中第一个不重复的字符

请实现一个函数用来找出字符流中第一个只出现一次的字符。例如，当从字符流中只读出前两个字符"go"时，第一个只出现一次的字符是"g"。当从该字符流中读出前六个字符“google"时，第一个只出现一次的字符是"l"。
输出描述:
如果当前字符流没有存在出现一次的字符，返回#字符。

• 最优解法：时间复杂度 O(n),空间复杂度 O(n)

// 核心代码：LinkedHashMap 是有序的 hashMap，可以找到出现一次的字符并且满足是第一个出现
private Map<Character, Integer> map = new LinkedHashMap<>();
public void Insert(char ch) {
    if (map.containsKey(ch)) {
        map.put(ch, 0);
    } else {
        map.put(ch, 1);
    }
}
public char FirstAppearingOnce() {
    for (Map.Entry<Character, Integer> en : map.entrySet()) {
        if (en.getValue() == 1) {
            return en.getKey();
        }
    }
    return '#';
}

---

数组中只出现一次的数字

一个整型数组里除了两个数字之外，其他的数字都出现了两次。请写程序找出这两个只出现一次的数字。

public void FindNumsAppearOnce(int [] array,int num1[] , int num2[]) {
    Map<Integer, Integer> map = new HashMap<>();
    for (int i = 0; i < array.length; i++) {
        int t = array[i];
        if (map.containsKey(t)) {
            map.put(t, 2);
        } else {
            map.put(t, 1);
        }
    }
    boolean flag = true;
    for (Map.Entry<Integer, Integer> en : map.entrySet()) {
        if (en.getValue() == 1) {
            if (flag) {
                num1[0] = en.getKey();
                flag = false;
            } else {
                num2[0] = en.getKey();
            }
        }
    }
}

---

第一个只出现一次的字符

在一个字符串(1<=字符串长度<=10000，全部由字母组成)中找到第一个只出现一次的字符,并返回它的位置

• 字符串长度可能比较长，所以第一不转字符数组，大数组会占用很多内存空间，第二字符串长度很长时遍历比较费时，所以我们只遍历一次。

public int FirstNotRepeatingChar(String str) {
    if (str == null || str.length() == 0) {
        return -1;
    }
    // 能放得下所有大小写字母即可
    int[] arr = new int['z' + 1];
    for (int i = 0; i < str.length(); i++) {
        arr[str.charAt(i)]++;
    }
    // 存放所有只出现一次的字母在字符串中的索引
    ArrayList<Integer> res = new ArrayList<>();
    for (int i = 0; i < arr.length; i++) {
        if (arr[i] == 1) {
            res.add(str.indexOf(i));
        }
    }
    int index = 9999;
    for (int i = 0; i < res.size(); i++) {
        if (res.get(i) < index) {
            index = res.get(i);
        }
    }
    return res.size() == 0 ? 0 : index;
}

---