【1错1对0】字符流中第一个非重复字符

https://www.nowcoder.com/practice/00de97733b8e4f97a3fb5c680ee10720?tpId=13&tqId=11207&tPage=1&rp=1&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking

日期	是否一次通过	comment
2019-02-09 20:20	N	懵了，最蠢的方法都没想到
2019-02-10 12:20	Y	感叹下char自动转成int作为asc数组的下标，真方便

题目：RT
思路：

1. Map中存char以及出现次数，第一个只出现1次的char为所求；
2. 把char转成ascii码，作为数组的下标，出现次数作为数组对应位置的值，第一次出现1的位置即为所求。(char转ascii在java中可以自动转换，即char转int，不需要额外的操作)

1. HashMap

import java.util.*;
public class Solution {
    //Insert one char from stringstream
    Map<Character, Integer> chrTimes = new HashMap<>();
    ArrayList<Character> chars = new ArrayList<>();
     
    public void Insert(char ch)
    {
        chrTimes.put(ch, chrTimes.getOrDefault(ch, 0) + 1);
        chars.add(ch);
    }
  //return the first appearence once char in current stringstream
    public char FirstAppearingOnce()
    {
        for(char c : chars) {
            if(chrTimes.get(c) == 1) {
                return c;
            }
        }
        return '#';
        
    }
}

2. 数组转ASCII法

import java.util.*;
public class Solution {
    //Insert one char from stringstream
    ArrayList<Character> chars = new ArrayList<>();
    int[] ascCounts = new int[256];
    
    public void Insert(char ch)
    {
        ascCounts[ch] += 1;
        if(ascCounts[ch] == 1) {
            chars.add(ch);  // 只存第一次即可
        }
        
    }
  //return the first appearence once char in current stringstream
    public char FirstAppearingOnce()
    {
        for(char c : chars) {
            if(ascCounts[c] == 1) {
                return c;
            }
        }
        return '#';
       
    }
}

扩展：

参考：https://blog.csdn.net/L_X_Y_HH/article/details/81252756

1. 第一个只出现一次的字符：
   在一个字符串（0 <= 字符串长度 <= 10000,全部由字母组成）中找到第一个只出现一次的字符，并返回它的位置，如果没有则返回-1

2. 数组中数字出现的次数：
   一个数组里除了两个数字外，其他数字都出现了两次，请写程序找出这两个只出现一次的数字，要求时间复杂度为O(n)，空间复杂度为O(1)

3. 数组中唯一只出现一次的数字：
   在一个数组中除一个数字只出现一次外，其他数字都出现三次，请找出那个只出现一次的数字

出现两次，，用异或或者 分组异或；出现三次，则用对应位做整除3.

对于扩展2，具体来说：

1. 所有数字异或；
2. 获取异或结果最低位为1的位数k；
3. 根据位数将数组分开：第k位为1和不为1
4. 将上述两组数字分别全部异或，得到的两个数字即为所求
   代码如下：

import java.util.*;
public class Solution {
    public void FindNumsAppearOnce(int[] array,int num1[] , int num2[]) {
        int fstNonZeroBit = getFstNonZeroBit(array);
        ArrayList<ArrayList<Integer>> part = partIntoTwoArray(array, num1, num2, fstNonZeroBit);
        genAppearOnce(num1, part.get(0));
        genAppearOnce(num2, part.get(1));
    }
    
    private int getFstNonZeroBit(int[] array) {
        int xorVal = 0;
        for(int i: array) {
            xorVal ^= i;
        }
        
        int fstNonZeroBit = 0;
        while(xorVal != 0) {
            if((xorVal & 1) == 1) {
                break;
            }
            fstNonZeroBit ++;
            xorVal >>= 1;
        }
        
        return fstNonZeroBit;
    }
    
    
    private ArrayList<ArrayList<Integer>> partIntoTwoArray(int[] array,int num1[] , 
                                  int num2[], int fstNonZeroBit) {
        ArrayList<Integer> temp1 = new ArrayList<>();
        ArrayList<Integer> temp2 = new ArrayList<>();
        for(int i: array) {
            if(((i>>fstNonZeroBit) & 1) == 1) {
                temp1.add(i);
            } else {
                temp2.add(i);
            }
        }
        
        ArrayList<ArrayList<Integer>> res = new ArrayList<>();
        res.add(temp1);
        res.add(temp2);
        
        return res;
    }
    
    private void genAppearOnce(int[] num1, ArrayList<Integer> partArray) {
        int xorVal = 0;
        for(int i: partArray) {
            xorVal ^= i;
        }
        
        num1[0] = xorVal;
    }
}

值得注意的是异或初值为0：
int xorVal = 0;