字符串问题——判断字符数组中是否所有字符都只出现一次

Posted on | In ,

给定一个字符类型数组chas，判断是否所有字符都只出现过一次。用以下两种要求实现：
要求1：时间复杂度为O(N)。
要求2：在确保额外空间复杂度为O(1)的情况下，实现尽量时间复杂度低的算法。

实现：
要求1：遍历chas，用boolean类型数组（也可用哈希表）记录相应chas字符数组中每种字符是否出现一次，若map[chas[i]]==true，表示已经有一个与chas[i]值相同的字符存在，返回false。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
public class IsUnique {
	/**
	 * 方法一：遍历数组，时间复杂度O(1)
	 * @param str
	 * @return
	 */
	public static boolean isUnique1(String str) {
		if(str == null || str.equals("")) {
			return true;
		}
		char[] chas = str.toCharArray();
		//boolean[] map = new boolean[98]; //A的ASCII码为65，a的ASCII码为97
		boolean[] map = new boolean[256];
		for (int i = 0; i < chas.length; i++) {
			if (map[chas[i]]) {
				return false;
			}
			map[chas[i]] = true;
		}
		return true;
	}
	public static void main(String[] args) {
		System.out.println(isUnique1("aba"));
	}
}