面试题——字符串中的字符是否唯一

题目：Implement an algorithm to determine if a string has all unique characters What ifyou can not use additional data structures?

闲话不说，直接上代码（java），代码中有注释说明

package moree;

import java.util.Arrays;
import java.util.Scanner;

/**
 * Implement an algorithm to determine if a string has all unique characters
 * What if you can not use additional data structures?
 */
public class CheckUnique {
	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		System.out.println("Enter a string:");
		String str = in.nextLine();
		System.out.println("method1:"+isUniqueChars1(str));
		System.out.println("method2:"+isUniqueChars2(str));
		System.out.println("method3:"+isUniqueChars3(str));
		System.out.println("method4:"+isUniqueChars4(str));
	}

	/**
	 * 用hash的方法，将字符串中的每个字母哈希到表中 的某个位置，如果产生冲突，检查这个元素
	 * 的值是否与此位置的元素值相同，如果是证明有相同的字母，返回false，如果不是就采用链地 址 法解决冲突。这种方法使用了额外的存储空间
	 */
	public static boolean isUniqueChars1(String str) {
		// 我们使用链地址法来解决冲突，所以hash表的长度与字符串长度差不多即可,这里我取字符
		// 串长度的1.1倍——这个如果大牛看到的话可以给点指教，到底多少最高效
		int strLen = str.length();
		HashElement[] hashTable = new HashElement[(int) 1.1 * strLen];
		int tableLen = hashTable.length;
		for (int i = 0; i < strLen; i++) {
			char ch = str.charAt(i);
			HashElement element = new HashElement(ch, null);
			int index = ch % tableLen; // 用余数法求得元素在hash表中的位置索引
			if (hashTable[index] == null) {
				hashTable[index] = element;
			} else {
				HashElement temp = hashTable[index];
				if (ch == temp.data) {
					return false; // 如果这个字母已经在表中，立即返回false
				}
				while(temp.next!=null){
					temp  = temp.next;
					if(ch==temp.data){
						return false;
					}
				}
				temp.next = element;
			}
		}
		return true;
	}

	/**
	 * hash表中的元素
	 */
	static class HashElement {
		char data;
		HashElement next;

		public HashElement(char data, HashElement next) {
			super();
			this.data = data;
			this.next = next;
		}
	}

	/**
	 * 这是一个空间换时间的方案，实现比较简单
	 */
	public static boolean isUniqueChars2(String str) {
		boolean[] check = new boolean[256];// 假设字符串中的字母都 可以用ascii编码——都是英文字母
		for (int i = 0; i < str.length(); i++) {
			if (check[str.charAt(i)]) {
				return false;
			}
			check[str.charAt(i)] = true;
		}
		return true;
	}

	/**
	 * 这是一个蛮力算法：从第一个字母开始遍历，拿它和后面所有的字母比较，如果有与之相同的字母即返回
	 * false。此算法不用额外的空间，时间复杂度为O(n^2)
	 */
	public static boolean isUniqueChars3(String str) {
		char[] chars = str.toCharArray(); // 为了避免重复运算，先把字符串中的字符提取到一个数组中
		for (int i = 0; i < chars.length - 1; i++) {
			for (int j = i + 1; j < chars.length; j++) {
				if (chars[i] == chars[j]) {
					return false;
				}
			}
		}
		return true;
	}
	
	/**
	 * 我们选对字符串中的字母进行排序，然后比较相信元素是否相等，如果所有相信的元素都 不同，则返回true,
	 * 这个算法的时间复杂度和所需的空间由排序算法决定。
	 */
	public static boolean isUniqueChars4(String str){
		char[] chars = str.toCharArray();
		Arrays.sort(chars);
		for(int i=0;i<chars.length-1;i++){
			if(chars[i] ==chars[i+1]){//相邻字符相等
				return false;
			}
		}
		return true;
	}
	
}

欢迎各位指正。。。