面试题目字符统计

有人问：

求第一个无重复字符,如"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;
            }
        }

    }
}

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

一次遍历，统计每个字符出现次数，保持有序。第一个出现次数为1的就是。效率O(n)

	public static void main(String arg[]){
		String test = "tatle";
		char[] array = test.toCharArray();
		LinkedHashMap<String, Integer> map = new LinkedHashMap<String, Integer>();
		for(char tmp : array){
			String str = tmp+"";
			if(map.get(str)==null){
				map.put(str, 1);
			}else{
				map.put(str, 0);
			}
			
		}
	
		for(Entry<String, Integer> tmp : map.entrySet()){
			if(tmp.getValue()!=null&&tmp.getValue()==1){
				System.out.println(tmp.getKey());
				break;
			}
		}
		
	}

异常大大用了流程形式，没面向对象~~~

你打算娶个什么对象回家?

我只是提醒一下java api 中还有linkedmap这种东西的存在.这题是专门为这个类定制的....

被同事ＢＳ了

	public static void main(String arg[]){
		String test = "tatleae";
		char[] array = test.toCharArray();

		for(char tmp : array){
	
			if(test.indexOf(tmp)==test.lastIndexOf(tmp)){
				System.out.println(tmp);
				break;
			}
		}
	}

哈哈 ，这种util类型的东西，每次开始都是一大把的代码，很多年过去剩下的，都是区区几行，勾起很多回忆 ～_～

尤其是一些关于time的，string的，check之类，现在都有很多回头乐的故事

不过String里面那一堆堆的loop，还算O（n）么？

不知道我的想法行不行.........

public class Test
{
    public static void main(String[] args)
    {
        Set tempSet = new LinkedHashSet();

        String tempStr = new String("tesabet");

        for (int i = 0; i < tempStr.length(); i++)
        {

            tempSet.add(tempStr.toCharArray()[i]);

        }

        Iterator it = tempSet.iterator();

        int i = 0;

        while (it.hasNext())
        {

            if ((it.next().toString()).toCharArray()[0] != tempStr
                .toCharArray()[i])

            {

                System.out.print((i + 1) + " " + tempStr.toCharArray()[i]);

                break;
            }

            if (i == tempSet.size() - 1)
            {
                System.out.print((i + 1) + " " + tempStr.toCharArray()[i + 1]);
            }

            i++;

        }

    }

}

 

这个的复杂度应该是N平方了

linkedmap,学习了！
高手果然就是高手！
如果我要对字符出现的次数按照从大到小的次序排序各位的方法就很不好扩展了！