Hash求index的问题
今天看了一篇关于Hash的文章有如下疑问疑问1、
是一个问题
文章给出的也是hash
比如从“one day i will success”中查找 will
最简单的做法就是用split分割字符串 比较 如果用hash的话也得一个个单词遍历，求Index 这样效率会高吗？
问题2、我昨天发的一个帖子 一道面试题，希望各位能给我出最优解
http://bbs.csdn.net/topics/390277569
还有，我现在打算学hadoop 谁能给个学习路线。或者一个比较好的教程。能给我一个去公司实习的机会更好
--------------------编程问答-------------------- 顶楼主，我现在还没学那么多···
--------------------编程问答--------------------
顶顶顶顶顶顶顶顶顶顶
--------------------编程问答--------------------
如果是字符找字符的话，正则估计会快些；如果是字符数组的话，直接遍历还是算挺快的，似乎也没什么更快的方法了。或者你可以考虑一些加些算法来查询，比如二叉树、二分法等等 --------------------编程问答-------------------- 谁有好的解法 --------------------编程问答-------------------- 难道楼主要做毕设？ --------------------编程问答-------------------- 没呢 毕设题目还没定呢 过段时间回学校再定毕设题目 就是想知道这个题的解法 --------------------编程问答-------------------- 除 --------------------编程问答-------------------- 我来讲讲我的想法，不一定对。
【问题一】
假设字串的规模是n个字串，每个字串平均长度是m，那么hash和Trie树均为：预处理时间O(nm)，查找每个字串时间O(m)
二者效率接近，但是Trie树不用考虑解决地址冲突，编程复杂度较小。
【问题二】
这个问题最好的做法是并查集，时间复杂度是O(mα(n,m))，相当于O(m)。实现如下（屏幕输入输出）：
class Element{
private Element father = this;
Element(){
}
Element getFather(){
if (father == this) return this;
father = father.getFather();
return father;
}
void setFather(Element father_){
father = father_;
}
}
public class UnionSet {
private Element[] elements;
private int parts;
public UnionSet(){
}
public UnionSet(int n){
parts = n;
elements = new Element[n];
for (int i = 0; i< n; i++)
elements[i] = new Element();
}
public boolean isInCommon(int index_1, int index_2){
return elements[index_1].getFather() == elements[index_2].getFather();
}
public void union(int index_1, int index_2){
if (!isInCommon(index_1, index_2)){
parts--;
elements[index_1].setFather(elements[index_2]);
}
}
public int getParts(){
return parts;
}
}
import java.util.Scanner;
public class TestUnionSet {
public static void main(String[] args){
Scanner read = new Scanner(System.in);
int n = read.nextInt();
int m = read.nextInt();
UnionSet Friends = new UnionSet(n);
for (int i = 0; i < m; i++){
int x = read.nextInt();
int y = read.nextInt();
Friends.union(x-1, y-1);
}
System.out.println(Friends.getParts());
read.close();
}
}
补充：Java , Java SE
