解
第一步，万年不变的查错。如果给的array是null或空，直接return
public ListNode[] rehashing(ListNode[] hashTable) {
if (hashTable == null || hashTable.length == 0) {
return hashTable;
}
...
}
题目就是rehash，没什么复杂的算法，连hash的方式题目里都有了。就是先建一个比原来大一倍的新list
int newCapacity = hashTable.length * 2;
ListNode[] newTable = new ListNode[newCapacity];
然后旧table里每一个element都是一个LinkedList，遍历一下，每一个都重新算一个hash。用刚hash出来的index去新的table找，如果没有就建一个新的LinkedList，如果有就加到list最后。最后return新的table就好了。
for (int i = 0; i < hashTable.length; i++) {
while (hashTable[i] != null) {
// rehash
int newIndex = (hashTable[i].val % newCapacity + newCapacity) % newCapacity;
if (newTable[newIndex] == null) {
newTable[newIndex] = new ListNode(hashTable[i].val);
} else {
ListNode dummy = newTable[newIndex];
while (dummy.next != null) {
dummy = dummy.next;
}
dummy.next = new ListNode(hashTable[i].val);
}
hashTable[i] = hashTable[i].next;
}
}
return newTable;
完整的code
/**
* Definition for ListNode
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) {
* val = x;
* next = null;
* }
* }
*/
public class Solution {
/**
* @param hashTable: A list of The first node of linked list
* @return: A list of The first node of linked list which have twice size
*/
public ListNode[] rehashing(ListNode[] hashTable) {
if (hashTable == null || hashTable.length == 0) {
return hashTable;
}
int newCapacity = hashTable.length * 2;
ListNode[] newTable = new ListNode[newCapacity];
for (int i = 0; i < hashTable.length; i++) {
while (hashTable[i] != null) {
// rehash
int newIndex = (hashTable[i].val % newCapacity + newCapacity) % newCapacity;
if (newTable[newIndex] == null) {
newTable[newIndex] = new ListNode(hashTable[i].val);
} else {
ListNode dummy = newTable[newIndex];
while (dummy.next != null) {
dummy = dummy.next;
}
dummy.next = new ListNode(hashTable[i].val);
}
hashTable[i] = hashTable[i].next;
}
}
return newTable;
}
};
分析
时间复杂度
如果总共有n个element，那遍历就是O(n)，插入到LinkedList的是每个O(k)，k是LinkedList的size。不过因为collision不常发生，所以期望的复杂度还是O(n)，最坏是O(n2)。
空间复杂度
一共n个element，新的table是它的两倍，那也是O(n)。
这个题挺无聊的。嗯。
