W***u
发帖数: 81 | 1 原题是,Write a method to sort an array of strings so that all the anagrams
are next to each other.
看到的靠谱的方法是 先 sort 每一个string，然后给每一个sorted后的string
generate 一个key 然后用hashtable 来找到 anagrams的String. 我的问题是这个hash
table 如何生成，能够保证，解决conflicts，并且保证O(1)的查找呢？
本人菜鸟，对hashtable的理解还在寻找hash function 然后每一个key 对应一个
value的层次。简单的就是在知道key的范围的时候用数组实现，当不知道key值范围的
时候就不知道怎么搞了？ 看到C++里的hashtable 实现都是 按照pair 插
入进去的，真心不知道这样的查找怎么能够保证O(1).
求各位前辈高人解疑释惑。 拜谢！ |
p*****2
发帖数: 21240 | 2
hash
不是150上的题吗？面试不会考吧？我从来没想过这题。
【在 W***u 的大作中提到】
: 原题是,Write a method to sort an array of strings so that all the anagrams
: are next to each other.
: 看到的靠谱的方法是 先 sort 每一个string，然后给每一个sorted后的string
: generate 一个key 然后用hashtable 来找到 anagrams的String. 我的问题是这个hash
: table 如何生成，能够保证，解决conflicts，并且保证O(1)的查找呢？
: 本人菜鸟，对hashtable的理解还在寻找hash function 然后每一个key 对应一个
: value的层次。简单的就是在知道key的范围的时候用数组实现，当不知道key值范围的
: 时候就不知道怎么搞了？ 看到C++里的hashtable 实现都是 按照pair 插
: 入进去的，真心不知道这样的查找怎么能够保证O(1).
: 求各位前辈高人解疑释惑。 拜谢！
|
M**********7
发帖数: 378 | 3 一般面试Java C#不需要实现哈希。
对于哈希算法单独准备一下各种情况的应对和原理，有兴趣的话找语言中的实现代码读
一下。
hash
【在 W***u 的大作中提到】
: 原题是,Write a method to sort an array of strings so that all the anagrams
: are next to each other.
: 看到的靠谱的方法是 先 sort 每一个string，然后给每一个sorted后的string
: generate 一个key 然后用hashtable 来找到 anagrams的String. 我的问题是这个hash
: table 如何生成，能够保证，解决conflicts，并且保证O(1)的查找呢？
: 本人菜鸟，对hashtable的理解还在寻找hash function 然后每一个key 对应一个
: value的层次。简单的就是在知道key的范围的时候用数组实现，当不知道key值范围的
: 时候就不知道怎么搞了？ 看到C++里的hashtable 实现都是 按照pair 插
: 入进去的，真心不知道这样的查找怎么能够保证O(1).
: 求各位前辈高人解疑释惑。 拜谢！
|
W***u
发帖数: 81 | 4 不是150上的
【在 p*****2 的大作中提到】
:
: hash
: 不是150上的题吗？面试不会考吧？我从来没想过这题。
|
M**********7
发帖数: 378 | 5 第四版9.2
话说回来，在工作的还要背题真的挺悲催的，工作中的问题和这些问题基本没交集，就
是hashmap用的多。
【在 W***u 的大作中提到】
: 不是150上的
|
r**d
发帖数: 316 | 6 仍然按照一般的排序办法给字符串数组排序，只是判断两个字符串大小时候，不比较字
符串本身，而是比较两个字符串的字母拆开重新排序后形成的两个字符串。
这样anagram就会排在一起。
hash
【在 W***u 的大作中提到】
: 原题是,Write a method to sort an array of strings so that all the anagrams
: are next to each other.
: 看到的靠谱的方法是 先 sort 每一个string，然后给每一个sorted后的string
: generate 一个key 然后用hashtable 来找到 anagrams的String. 我的问题是这个hash
: table 如何生成，能够保证，解决conflicts，并且保证O(1)的查找呢？
: 本人菜鸟，对hashtable的理解还在寻找hash function 然后每一个key 对应一个
: value的层次。简单的就是在知道key的范围的时候用数组实现，当不知道key值范围的
: 时候就不知道怎么搞了？ 看到C++里的hashtable 实现都是 按照pair 插
: 入进去的，真心不知道这样的查找怎么能够保证O(1).
: 求各位前辈高人解疑释惑。 拜谢！
|
W***u
发帖数: 81 | 7 谢谢LS各位回答，有人能指点第二点问的关于 hashtable的问题么？ 谢谢！ |
h*****3
发帖数: 1391 | 8 c++里面是用map,复杂度是O(nlogn),是用tree实现的。没有hash的直接函数。 |
M**********7
发帖数: 378 | |
w****f
发帖数: 684 | 10 有没有C++ 的hashtable implementation？
【在 h*****3 的大作中提到】
: c++里面是用map,复杂度是O(nlogn),是用tree实现的。没有hash的直接函数。
|
f*******n
发帖数: 12623 | 11 TR1 或 C++11里有hash table
但是hash table也无法“保证O(1)的查找”。hash table的worst case是O(n)查找。
binary search tree的worst case是O(log n)
【在 w****f 的大作中提到】
: 有没有C++ 的hashtable implementation？
|
W***u
发帖数: 81 | |
