面试题目字符统计

有人问：

求第一个无重复字符,如"total"的第一个无重复字符是o,"teeter"的第一个无重复字符是r,效率要优于O(n的平方)
public static Character FirstNonRepeated(String)

 

 

说句实话，形如这样的字符串统计规律(什么按字符出现次数排序之类的)的题目，在笔试题目中屡见不鲜，在论坛里面总是有人在问。
笔试是关键，笔试不行，大公司想都不要想了。
这里面方法有很多种，我有一种方法，面向对象的，可解此类问题！

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashSet;
import java.util.Iterator;
import java.util.List;

public class Tongji {

    /**
     * @param args
     */
    char ch;

    int count = 1;

    int index;

    public Tongji(char ch, int index) {
        this.ch = ch;
        this.index = index;
    }

    @Override
    public int hashCode() {//eclipse自动生成的
        final int PRIME = 31;
        int result = 1;
        result = PRIME * result + ch;
        result = PRIME * result + count;
        return result;
    }

    @Override
    public boolean equals(Object obj) {
        if (this == obj)
            return true;
        if (obj == null)
            return false;
        if (getClass() != obj.getClass())
            return false;
        final Tongji other = (Tongji) obj;
        if (ch != other.ch)
            return false;
        if (count == other.count) {
            other.count++;

        }
        return true;
    }

    public static void main(String[] args) {
        String a = "total";
        HashSet set = new HashSet();
        for (int i = 0, k = a.length(); i < k; i++) {
            set.add(new Tongji(a.charAt(i), i));
        }
        List list = new ArrayList(set);
        Collections.sort(list, new Comparator() {//按索引排序
            public int compare(Object o1, Object o2) {
                Tongji t1 = (Tongji) o1;
                Tongji t2 = (Tongji) o2;

                if (t1.index > t2.index)
                    return 1;
                return 0;
            }
        });

        for (Iterator it = list.iterator(); it.hasNext();) {
            Tongji tj = (Tongji) it.next();
            if (tj.count == 1) {
                System.out.println("char:" + tj.ch + " count:" + tj.count);
                break;
            }
        }

    }
}

 这就是面向对象的强大威力！

评论

60 楼 yyf16 2010-01-13  

<p> </p>
<pre name="code" class="java">import java.util.HashMap;
import java.util.Map;


public class firstNonRepeatedChar  {

    public static void main(String args[]) {
        String s = "tbbbotoal";
        Map map = new HashMap();       
        char[] charArgs = s.toCharArray();
        char flag = ' ';
        for(char c : charArgs){
           
            if(!map.containsKey(c) &amp;&amp; flag != c){
                map.put(c, "value");
            } else {
                map.remove(c);
                flag = c;
            }
        }
       
        System.out.println(map.keySet().toArray()[0]);
    }
}</pre>
<pre name="code" class="java">输出：a</pre>

59 楼 piao_bo_yi 2010-01-11  

asd 写道

这种字符统计，必然是一个255大小的状态数组啊，在c程序员看来都是拿不出手的题目，用什么库函数啊。

“箱子排序”果然是这种问题的通解啊~~~

58 楼 piao_bo_yi 2010-01-11  

piao_bo_yi 写道

asd 写道

这种字符统计，必然是一个255大小的状态数组啊，在c程序员看来都是拿不出手的题目，用什么库函数啊。

可是得输出第一个不重复的字符啊，你的方法能行么？？

明白了，原来能行。

57 楼 piao_bo_yi 2010-01-11  

asd 写道

这种字符统计，必然是一个255大小的状态数组啊，在c程序员看来都是拿不出手的题目，用什么库函数啊。

可是得输出第一个不重复的字符啊，你的方法能行么？？

56 楼 asd 2009-12-02  

这种字符统计，必然是一个255大小的状态数组啊，在c程序员看来都是拿不出手的题目，用什么库函数啊。

55 楼 yfkscu 2009-12-02  

<p>一个时间复杂度为n的算法。第一次发帖有什么不足之处还请指教哈！</p>
<p> </p>
<pre name="code" class="java">//一个时间复杂度为n的算法

import java.util.HashMap;
import java.util.Iterator;
import java.util.Map.Entry;

public class TestClass {
public static void main(String[] args) {
HashMap&lt;Character, Integer&gt; map = new HashMap&lt;Character, Integer&gt;();
String str = "kabcdabc";
int len = str.length();
for (int i = 0; i &lt; len; i++) {
char c = str.charAt(i);
if (map.containsKey(c)) {
map.remove(c);
} else {
map.put(c, i);
}
}

int minIndex = len;
Entry&lt;Character, Integer&gt; minEntry = null;
for (Iterator&lt;Entry&lt;Character, Integer&gt;&gt; iter = map.entrySet()
.iterator(); iter.hasNext();) {
Entry&lt;Character, Integer&gt; entry = iter.next();
if (entry.getValue() &lt; minIndex) {
minEntry = entry;
}
}
System.out.println(minEntry.getKey());
}
}
</pre>
<p> 输出结果为：</p>
<p>k</p>

54 楼 sbkyv 2009-08-18  

最好不要把count放在循环里！犯了错误

53 楼 sbkyv 2009-08-18  

           来个php的
            $old =str_split("eerrttyyf");
            $chars = array_flip($old);
            $l = count($old);
            for($i=0;$i<$l;$i++){
                if($i==$chars[$old[$i]]){
                    echo($old[$i]);
                    break;
                }
                else
                {
                    $chars[$old[$i]]=0;
                }
            }

52 楼 rabbitbug 2009-08-17  

这种算法题，就不是让你用java类库来做的，肯定是要用最简单的东西，一用到类库效率要低好几个等级

51 楼 gowish 2009-08-05  

还一种更快的：
private static char getDuplicateChr2(String param) {
char[] chrList = param.toCharArray();
for (int i=0;i<chrList.length;i++) {
if (param.indexOf(chrList[i]) == param.lastIndexOf(chrList[i])) {
return chrList[i];
}
}
return ' ';
}

50 楼 gowish 2009-08-05  

private static char getDuplicateChr(String param) {
char[] chrList = param.toCharArray();
List<Character> unique = new ArrayList<Character>();
for(int i=0;i<chrList.length;i++) {
if (unique.contains(chrList[i])) {
continue;
} else {
int index = param.indexOf(chrList[i]);
            if (index == i) {
                if (-1 != param.substring(index+1).indexOf(chrList[i])) {
                unique.add(chrList[i]);
                continue;
                } else {
                return chrList[i];
                }
            } else {
            break;
            }
}
}
return ' ';
}

49 楼 kukuqiu001 2009-07-20  

我是根据异常兄的linkedHashMap改写的
统计字符串里面每个字母出现的频率

import java.util.LinkedHashMap;
import java.util.Map.Entry;


public class CountCharInString {

	public static void main(String[] args) {
       String str ="total";
       char[] charArr = str.toCharArray();
       LinkedHashMap<String, Integer> linkedMap = new LinkedHashMap<String, Integer>();
       int count=1;
       for(char ch: charArr){
    	   String chStr = ch+"";
    	   if(linkedMap.get(chStr)!=null){
    		   linkedMap.put(chStr, linkedMap.get(chStr)+1);
    	   }else{
    		   linkedMap.put(chStr, count);
    	   }
    	   
       }
       
       for(Entry<String, Integer> temp : linkedMap.entrySet()){
    	 if(temp.getValue()!=null && temp.getKey()!=null){
    		 System.out.println("key =" + temp.getKey()+",value ="+ temp.getValue());
    	 }
       }
	}

}

48 楼 cy729215495 2009-07-17  

google_fans 写道

cy729215495 写道

而且这是笔试题目，笔试是有时间限制的，用这些最底层的代码来写做这样的题目，
花的时间很长。当然现在不是笔试，你可以在机器上面运行无数遍了然后把代码贴过来，
我们要的是速度和规则来解这类题目，凡事有规律了，当然就好做了！

这个题目的C语言版本很快的，熟悉的人几分钟就OK了。

比如说一个题目需要用hash表来解决，一个人是用c语言实现了自己的hash结构，一个人是用的类库。
你喜欢哪个人？

哦？就算是熟悉的人碰到这样的题目了，用算法几分钟就能搞定的人并不多吧。

47 楼 clx_wq 2009-07-16  

String str="toaltoa";

for(int i=0; i<str.length(); i++){
int count=0;
for(int j=0; j<str.length(); j++){
if(String.valueOf(str.charAt(i)).equals(String.valueOf(str.charAt(j)))){
count+=1;
}
}
if(count==1){
System.out.print(str.charAt(i));
break;
}
}

46 楼 google_fans 2009-06-05  

cy729215495 写道

而且这是笔试题目，笔试是有时间限制的，用这些最底层的代码来写做这样的题目，
花的时间很长。当然现在不是笔试，你可以在机器上面运行无数遍了然后把代码贴过来，
我们要的是速度和规则来解这类题目，凡事有规律了，当然就好做了！

这个题目的C语言版本很快的，熟悉的人几分钟就OK了。

比如说一个题目需要用hash表来解决，一个人是用c语言实现了自己的hash结构，一个人是用的类库。
你喜欢哪个人？

45 楼 google_fans 2009-06-05  

case0079 写道

那个C程序是用空间换时间.
实际使用中感觉还是LINKEDHASHMAP稳定些.

这个空间开销很小的

如果有中文，开销要大些

44 楼 yzzh9 2009-06-03  

统计重复个数的用上面那个c程序对应的java版改动一下就可以了：

public class firstNonRepeatedChar {
	private  static final int MAX_CHAR = 256;   
	
	public static void main(String[] args) {
		String str = "tootaddl";
		int count = firstNoRepeatedChar(str);
		System.out.println(count);
	}

	public static int firstNoRepeatedChar(String str) {
		 int i = 0;   
		 int j = 0;   
		 int count = 0;
		 int[] p = new int[MAX_CHAR]; 
		 char[] chars = str.toCharArray();
		 //初始化数组p，p用于保存字符出现的次数		 
		 for (j = 0; j < MAX_CHAR; j++) {   
		  p[j] = 0;   
		 } 
		 
		 //统计字符出现的次数	
		 for(i=0;i<chars.length;i++){
			 p[chars[i]]++;
		 }
		 
		 for(int n=0;n<MAX_CHAR;n++){
			 if(p[n]>1) count++;
		 }
		 return count;
	}
}

43 楼 wnzz95391511 2009-06-03  

我感觉像这样的笔试题，主要考察的还是效率方面，要首先以O(n)为基准点。
不使用类库的为好！
之前用C的那个程序和对应的JAVA版本，都挺好的。

42 楼 抛出异常的爱 2009-06-03  

cy729215495 写道

这么多的答案，我原本写这个程序是唤醒大家算法问题用面向对象的方法来做很好很强大，用c当然可以实现。

现在如果题目改为求统计重复字符串的个数，怎么做呢？希望大家接着往下面做！

个数不爽....

最长自反字符串好玩一些.
abcdeacdrtt=>cd(2)

41 楼 merman 2009-06-03  

<div class="quote_title">楼主 写道</div>
<div class="quote_div">
<pre name="code" class="java">    @Override
    public boolean equals(Object obj) {
        if (this == obj)
            return true;
        if (obj == null)
            return false;
        if (getClass() != obj.getClass())
            return false;
        final Tongji other = (Tongji) obj;
        if (ch != other.ch)
            return false;
        if (count == other.count) {
            other.count++;

        }
        return true;
    }
</pre>
</div>
<p>我觉得equals不能这样来用，使用equals要满足 自反性 a.equals(a) is true; 对称性 a.equals(b) = b.equals(a); 传递性 a.equals(b) = true b.equals(c) = true 那么 a.equals(c) = true； 一致性 任何时候调用a.equals(b)得到的结果都是一样的。</p>