快速查找字符串中首个重复字母算法

找出字符串中出现的首个重复字母

例“abncdbmn”,首个重复字母为b

/**
 * 
 */
package com.tao.bao;

import java.util.HashMap;

/**
 * @author moon
 *
 */
public class StringFindSame {

	/**
	 * @param args
	 */
	public void findSameChar(char[] str){
		int length = str.length;
		for(int i = 0;i<length;i++)
			for(int j=i+1;j<length;j++)
			{
				if(str[i]==str[j]){
					System.out.println("-----"+str[i]);
					break;
				}
			}
	}
	
	public void findSameMap(char[] str){
		HashMap<Character, Integer> map = new HashMap<Character, Integer>();
		for(int i=0;i<str.length;i++){
			if(map.containsKey(str[i])){
				System.out.println("-----"+str[i]);
				break;
			}else
			{
				map.put(Character.valueOf(str[i]), Integer.valueOf(1));
			}
		}
	}
	
	public static void main(String[] args) {
		String str="adcbd";
		char findStr[] = str.toCharArray();
		
		StringFindSame same = new StringFindSame();
		//same.findSameChar(findStr);
		same.findSameMap(findStr);
	}

}

 

采用堆栈来实现，效果应该会更好。

第一种符合逻辑，第二种会导致结果不正确，以"abxba"为例。。。第一种正确地取到了a，第二种却取到了b

重复，干掉

	private static final Pattern p = Pattern.compile("(\\w).*\\1");

	private static String findDupChat(String s) {
		Matcher m = p.matcher(s);
		if (m.find()) {
			return m.group(1);
		} else {
			return null;
		}
	}

	public static void main(String[] args)
	{
		System.out.println(findDupChat("abcdefbef"));
		System.out.println(findDupChat("abcdefef"));
	}

比起数组实现，执行时间慢一个数量级。不过也算一种方法吧。

public void findSameMap(char[] str){ 
    HashMap<Character, Integer> map = new HashMap<Character, Integer>(); 
    for(int i=0;i<str.length;i++){ 
        if(map.containsKey(str[i])){ 
       
int n = map.get(Character.valueOf(str[i]), Integer.valueOf(1));
map.get(Character.valueOf(str[i]), n++);
        }else  { 
            map.put(Character.valueOf(str[i]), Integer.valueOf(1)); 
        } 
    }
   
     for(int i=0;i<str.length;i++){ 
        if(map.get(str[i])){        
int n = map.get(Character.valueOf(str[i]), Integer.valueOf(1));
if(n>=2){
return str[i];
}
        }
    }
} 

总结一下：

import java.util.BitSet;
import java.util.HashMap;
import java.util.regex.Matcher;
import java.util.regex.Pattern;


public class FindSameChar {

    public static char findSameChar(char[] str){  
        int length = str.length;  
        for(int i = 0;i<length;i++)  
            for(int j=i+1;j<length;j++)  
            {  
                if(str[i]==str[j]){  
                    return str[i];  
                }  
            }
        return 0;
    }  
      
    public static char findSameMap(char[] str){  
        HashMap<Character, Integer> map = new HashMap<Character, Integer>();  
        for(int i=0;i<str.length;i++){  
            if(map.containsKey(str[i])){
            	return str[i];
            }else  
            {  
                map.put(Character.valueOf(str[i]), Integer.valueOf(1));  
            }  
        }
        return 0;
    }
    
    public static char findSameBitSet(char[] str) {
    	BitSet set = new BitSet(255);
    	for (int i = 0; i < str.length; i++) {
    		if (set.get(str[i])) {
    			return str[i];
    		} else {
    			set.set(str[i], true);
    		}
    	}
    	return 0;
    }
    
    private static final Pattern p = Pattern.compile("(\\w).*\\1");  
    
    private static String findSameRegEx(String s) {  
        Matcher m = p.matcher(s);  
        if (m.find()) {  
            return m.group(1);  
        } else {  
            return null;  
        }  
    } 
    
    private static final long TIMES = 5000000;
	
	public static void main(String[] args) {
		char result = 0;
		long t = System.currentTimeMillis();
		for (long i = 0; i < TIMES; i++) {
			result = findSameChar("abcdefghijklmnopqrstbab".toCharArray());
		}
		t = System.currentTimeMillis() - t;
		System.out.println("findSameChar : Result " + result + " in " + t);
		
		result = 0;
		t = System.currentTimeMillis();
		for (long i = 0; i < TIMES; i++) {
			result = findSameMap("abcdefghijklmnopqrstbab".toCharArray());
		}
		t = System.currentTimeMillis() - t;
		System.out.println("findSameMap : Result " + result + " in " + t);

		result = 0;
		t = System.currentTimeMillis();
		for (long i = 0; i < TIMES; i++) {
			result = findSameBitSet("abcdefghijklmnopqrstbab".toCharArray());
		}
		t = System.currentTimeMillis() - t;
		System.out.println("findSameBitSet : Result " + result + " in " + t);
		
		String strResult = null;
		t = System.currentTimeMillis();
		for (long i = 0; i < TIMES; i++) {
			strResult = findSameRegEx("abcdefghijklmnopqrstbab");
		}
		t = System.currentTimeMillis() - t;
		System.out.println("findSameRegEx : Result " + strResult + " in " + t);
	}
} 

结果是：

findSameChar虽然快，不过不是楼主要的结果，findSameMap是楼主的要的结果，不过最慢。用BitSet比较符合要求。