给定一个字符串，求第一个不重复的字符

题目：

给定一个字符串，求第一个不重复的字符。例子：abbcdca 答案：d

如果用暴力解法，时间复杂度必然为 O(n2) ,而要达到 O(n) ,关键就是，利用所有字符的ASCII码都是在0~255之间，声明一个标记数组存放字符串的信息。

方法一：当字符串可以重复访问的时候，标记数组存放的是每个字符出现的次数。代码如下：

import java.util.Scanner;

/**
 * 给定一个字符串，求第一个不重复的字符 abbcad -> c
 * @author 木小草
 *
 */
public class Test01 {
public static void main(String[] args) {
        String tag = new String();
        Scanner scanner = new Scanner(System.in);
        tag = scanner.nextLine();
int[] flag = new int[256];
for (int i = 0; i < flag.length; i++) {
            flag[i] = 0;
        }
for (int i = 0; i < tag.length(); i++) {
            flag[tag.charAt(i)]++;
        }
for (int i = 0; i < tag.length(); i++) {
if (flag[tag.charAt(i)] == 1) {
                System.out.println(String.valueOf(tag.charAt(i)));
break;
            }
        }
    }
}

方法二：当字符串是流水字符串的时候，也就是字符串只能访问一次的时候，我们的标数组就应该保存字符串的小标了。代码如下：

import java.util.Scanner;

/**
 * 给定一个字符串，求第一个不重复的字符 abbcad -> c
 * @author 木小草
 *
 */
public class Test02 {
public static void main(String[] args) {
        String tag = new String();
        Scanner scanner = new Scanner(System.in);
        tag = scanner.nextLine();
int[] flag = new int[256];
for (int i = 0; i < flag.length; i++) {
            flag[i] = -1;
        }
for (int i = 0; i < tag.length(); i++) {
int index = tag.charAt(i);
if (flag[index]  >= 0) {
                flag[index] = -2;
            }else if(flag[index] == -1){
                flag[index] = i;
            }
        }
int min = 256;
for (int i = 0; i < flag.length; i++) {
if (flag[i] < 0) {
continue;
            }
if (min > flag[i]) {
                min = flag[i];
            }
        }
        System.out.println(tag.charAt(min));
    }
}

注意：转载请标明，转自itboy-木小草。
尊重原创，尊重技术。