《剑指offer》– 第一个只出现一次的字符、数组中只出现一次的数字、字符流中第一个不重复的字符、数组中重复的数字

一、第一个只出现一次的字符：

1、题目：

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

2、代码实现：

public class Test8 {
	public int FirstNotRepeatingChar(String str) {
		if(str.length()==0){
			return -1;
		}
		
		HashMap<Character, Integer> map = new HashMap<Character,Integer>();
		for(int i=0;i<str.length();i++){
			if(map.containsKey(str.charAt(i))){
				int time = map.get(str.charAt(i));
				map.put(str.charAt(i),++time);
			}else{
				map.put(str.charAt(i), 1);
			}
		}
		
		int pos=-1;
		for(int i=0;i<str.length();i++){
			char c = str.charAt(i);
			if(map.get(c)==1){
				return i;
			}
		}
		return pos;
    }
}

二、数组中只出现一次的数字：

1、题目：

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

2、解题思路：

参考牛客网的“披萨大叔”：https://www.nowcoder.com/questionTerminal/e02fdb54d7524710a7d664d082bb7811

首先：位运算中异或的性质：两个相同数字异或=0，一个数和0异或还是它本身。

当只有一个数出现一次时，我们把数组中所有的数，依次异或运算，最后剩下的就是落单的数，因为成对儿出现的都抵消了。

依照这个思路，我们来看两个数（我们假设是AB）出现一次的数组。我们首先还是先异或，剩下的数字肯定是A、B异或的结果，这个结果的二进制中的1，表现的是A和B的不同的位。我们就取第一个1所在的位数，假设是第3位，接着把原数组分成两组，分组标准是第3位是否为1。如此，相同的数肯定在一个组，因为相同数字所有位都相同，而不同的数，肯定不在一组。然后把这两个组按照最开始的思路，依次异或，剩余的两个结果就是这两个只出现一次的数字。

3、代码实现：

public class Test1 {

	//num1,num2分别为长度为1的数组。传出参数
	//将num1[0],num2[0]设置为返回结果
	public void FindNumsAppearOnce(int [] array,int num1[] , int num2[]) {
		 if(array==null ||array.length<2)
           return ;
		 
		 //对数组所有数组进行异或
		 int temp=0;
		 for(int i=0;i<array.length;i++){
			 temp^=array[i];
		 }
		 
		//从左向右移动，获取第一个为1的位数
		 int index=findFirstBits(temp);
		 
		 for(int i=0;i<array.length;i++){
			 if(isBit(array[i],index)){
				 num1[0]^=array[i];
			 }else{
				 num2[0]^=array[i];
			 }
		 }
    }

	
	private boolean isBit(int num, int indexOf1) {
		num = num >>indexOf1;
		return (num & 1) == 1;
	}


	//从左向右移动，获取第一个为1的位数
	private int findFirstBits(int num) {
		int indexBit = 0;
		while((num & 1)==0 && indexBit<(8<<2)){
			num = num>>1;//将num右移1位（也即除以2），然后再将结果赋值给num
			++indexBit;
		}
		
		return indexBit;
	}
}

三、字符流中第一个不重复的字符：

1、题目：

请实现一个函数用来找出字符流中第一个只出现一次的字符。例如，当从字符流中只读出前两个字符”go”时，第一个只出现一次的字符是”g”。当从该字符流中读出前六个字符“google”时，第一个只出现一次的字符是”l”。

2、解题思路：

一个字符占8位，因此不会超过256个，可以申请一个256大小的数组来实现一个简易的哈希表。时间复杂度为O(n)，空间复杂度O(n).

3、代码实现：

public class Test12 {
	//一个字符占8位，因此不会超过256个，可以申请一个256大小的数组来实现一个简易的哈希表。时间复杂度为O(n)，空间复杂度O(n).
	int[] hashtable = new int[256];//每一个位置初始值都是0
	StringBuilder builder = new StringBuilder();
	
	 //Insert one char from stringstream
    public void Insert(char ch){
        builder.append(ch);
        hashtable[ch] +=1;
    }
    //return the first appearence once char in current stringstream
    public char FirstAppearingOnce(){
    	char[] str = builder.toString().toCharArray();
    	for(char ch:str){
    		if(hashtable[ch]==1){
    			return ch;
    		}
    	}
    	return '#';
    }
}

四、数组中重复的数字：

1、题目：

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

2、代码实现：

public class Test22 {

	//第一种方法：
	//不需要额外的数组或者hashtable来保存，题目里写了数组里数字的范围保证在0 ~ n-1 之间，
	//所以可以利用现有数组设置标志，当一个数字被访问过后，可以设置对应位上的数 + n，之后再遇到相同的数时，
	//会发现对应位上的数已经大于等于n了，那么直接返回这个数即可。
	//将第一个重复的数字放在duplication的0号下标中。
	public boolean duplicate(int numbers[],int length,int [] duplication) {

		for(int i=0;i<length;i++){
			int index = numbers[i];
			
			if(index>=length){
				index = index-length;
			}
			if(numbers[index] >= length){
				duplication[0]=index;
				return true;
			}
			numbers[index]=numbers[index]+length;
		}
		return false;
	}
	
	
	//第二种方法：需要重新开拓一个数组
	public boolean duplicate1(int numbers[],int length,int [] duplication) {
		boolean[] k = new boolean[length];
		
		for(int i=0;i<length;i++){
			if(k[numbers[i]]==true){
				duplication[0]=numbers[i];
				return true; 
			}
			k[numbers[i]]=true;
		}
		return false;
	}
}