My code:
import java.util.*;
public class RandomizedSet {
private HashMap<Integer, Integer> map; // value -> index
private ArrayList<Integer> list; // value
private Random rand;
/** Initialize your data structure here. */
public RandomizedSet() {
map = new HashMap<Integer, Integer>();
list = new ArrayList<Integer>();
rand = new Random();
}
/** Inserts a value to the set. Returns true if the set did not already contain the specified element. */
public boolean insert(int val) {
if (map.containsKey(val)) {
return false;
}
else {
map.put(val, list.size());
list.add(val);
return true;
}
}
/** Removes a value from the set. Returns true if the set contained the specified element. */
public boolean remove(int val) {
if (!map.containsKey(val)) {
return false;
}
else {
int index = map.remove(val);
int last = list.remove(list.size() - 1);
if (last != val) {
list.set(index, last);
map.put(last, index);
}
return true;
}
}
/** Get a random element from the set. */
public int getRandom() {
int index = rand.nextInt(list.size());
return list.get(index);
}
}
/**
* Your RandomizedSet object will be instantiated and called as such:
* RandomizedSet obj = new RandomizedSet();
* boolean param_1 = obj.insert(val);
* boolean param_2 = obj.remove(val);
* int param_3 = obj.getRandom();
*/
這道題目沒有做出來芍殖。但還是很有意思的擂红。
我卡在了這里，
隨機返回一個數(shù)字围小。
我的問題是昵骤，如果加入了一些數(shù)字，有刪除了其中一些肯适，然后再隨機返回一個數(shù)字变秦，如果保證O(1)呢？
看了答案才知道框舔，List + Map
ArrayList 的本質(zhì)是 Array,
so list.remove(list.size() - 1) -> time complexity is only O(1)
http://stackoverflow.com/questions/24462513/time-complexity-for-java-arraylist-removeelement
The second point is that that the complexity of ArrayList.remove(index)
is sensitive to the value ofindex
as well as the list length.
The "advertised" complexity of O(N)
for the average and worst cases.
In the best case, the complexity is actually O(1)
. Really!
This happens when you remove the last element of the list; i.e. index == list.size() - 1
. That can be performed with zero copying; look at the code that @paxdiablo included in his Answer.
所以先把最后一個元素刪了蹦玫，然后再根據(jù)removed value去map里面找index，然后再去list里面刘绣，根據(jù)index重寫該value with last value in list
參考：
https://discuss.leetcode.com/topic/53235/java-with-hashset-arraylist
Anyway, Good luck, Richardo!
My code:
public class RandomizedSet {
Map<Integer, Integer> map = new HashMap<Integer, Integer>();
List<Integer> list = new ArrayList<Integer>();
Random r = new Random();
/** Initialize your data structure here. */
public RandomizedSet() {
}
/** Inserts a value to the set. Returns true if the set did not already contain the specified element. */
public boolean insert(int val) {
if (map.containsKey(val)) {
return false;
}
map.put(val, list.size());
list.add(val);
return true;
}
/** Removes a value from the set. Returns true if the set contained the specified element. */
public boolean remove(int val) {
if (!map.containsKey(val)) {
return false;
}
int removedIndex = map.get(val);
map.remove(val);
if (removedIndex < list.size() - 1) {
int tail = list.get(list.size() - 1);
list.set(removedIndex, tail);
map.put(tail, removedIndex);
}
list.remove(list.size() - 1);
return true;
}
/** Get a random element from the set. */
public int getRandom() {
return list.get(r.nextInt(list.size()));
}
}
/**
* Your RandomizedSet object will be instantiated and called as such:
* RandomizedSet obj = new RandomizedSet();
* boolean param_1 = obj.insert(val);
* boolean param_2 = obj.remove(val);
* int param_3 = obj.getRandom();
*/
這道題想復雜了樱溉。以為 get random 的時候是不允許重復的。但是刪除操作是允許重復的纬凤。其實不是福贞。所有的都不允許重復。
那就簡單了停士。
HashMap<Integer, Integer> 每個 value 只會對應一個index (在list中)
Anyway, Good luck, Richardo! -- 09/30/2016
