[leetcode]380. Insert Delete GetRandom O(1)设计数据结构，实现存，删，随机取的时间复杂度为O(1)

题目：

Design a data structure that supports all following operations in average O(1) time.

1.insert(val): Inserts an item val to the set if not already present.
2.remove(val): Removes an item val from the set if present.
3.getRandom: Returns a random element from current set of elements. Each element must have the same probability of being returned.
Example:

// Init an empty set.
RandomizedSet randomSet = new RandomizedSet();

// Inserts 1 to the set. Returns true as 1 was inserted successfully.
randomSet.insert(1);

// Returns false as 2 does not exist in the set.
randomSet.remove(2);

// Inserts 2 to the set, returns true. Set now contains [1,2].
randomSet.insert(2);

// getRandom should return either 1 or 2 randomly.
randomSet.getRandom();

// Removes 1 from the set, returns true. Set now contains [2].
randomSet.remove(1);

// 2 was already in the set, so return false.
randomSet.insert(2);

// Since 2 is the only number in the set, getRandom always return 2.
randomSet.getRandom();
思路：肯定是借助java已有的数据结构进行设计，常用的有ArrayList,HashMap,HashSet,能做到随机取数的有前两个，能实现判断和删除O（1）是否包含的是后两个，
而且map想判断的话，数据必须存key，这样就不能取数了。用list取数的时候，必须要知道数据和下标的对应关系，所以可以map和list配合

 1 * 没有一个现成的数据结构可以符合要求，但是可以组合使用它们实现，list存数据，map的key存数据，value存数据在list中的下标，

 2 * 这样ArrayList可以实现存O(1),删除借助map获取下标，实现O（1），判断重复用map的containsKey方法

 3 * 其实insert和remove，map都可以单独实现O（1），不单独用map就是因为无法实现getRandom，因为由于判断重复需要containsKey方法，所以数据必须存key而不是value

 4 * 但是随机取数时，map无法取出指定key，所以不能单独用map，随机取数只能用list，随机指定下标而取出数值

 5 * getRandom要求知道数据结构的大小，并且存储元素是相邻的

 6 public static void main(String[] args) {

 7         Q380InsertDeleteGetRandomO1 q = new Q380InsertDeleteGetRandomO1();

 8         q.set.insert(0);

 9         q.set.insert(1);

10         q.set.remove(0);

11         System.out.println(q.set.list);

12         System.out.println(q.set.map);

13         System.out.println(q.set.getRandom());

14     }

15     class RandomizedSet {

16         HashMap<Integer,Integer> map;

17         ArrayList<Integer> list;

18         /** Initialize your data structure here. */

19         public RandomizedSet() {

20             map = new HashMap();

21             list = new ArrayList<>();

22         }

23

24         /** Inserts a value to the set. Returns true if the set did not already contain the specified element. */

25         public boolean insert(int val) {

26             //判断是否包含可以用map或者set，但是set不能存下标

27             if (!map.containsKey(val))

28             {

29                 //key存数据，value存它在list中的下标

30                 map.put(val,list.size());

31                 list.add(val);

32                 return true;

33             }

34             else

35                 return false;

36         }

37

38         /** Removes a value from the set. Returns true if the set contained the specified element. */

39         public boolean remove(int val) {

40             if (map.containsKey(val))

41             {

42                 //删除：要想map中的value不用全部变，只能删除的时候list的下标不全部改变（list默认删除后后边的元素会向前挪），多以采取的方法：

43                 //先把list最后一个元素num覆盖到指定位置（借助map获取位置），再删除最后一个元素，然后map修改num的value，再删除val那条数据

44                 //最后一个元素

45                 int num = list.get(list.size()-1);

46                 //覆盖（也可以两个元素交换）

47                list.set(map.get(val),num);

48                //删除最后一个元素

49                list.remove(list.size()-1);

50                //改变num的下标

51                map.put(num,map.get(val));

52                //删除val这条数据

53                map.remove(val);

54                return true;

55             }

56             else

57                 return false;

58         }

59

60         /** Get a random element from the set. */

61         public int getRandom() {

62             Random random = new Random();

63             //随机获取下标进行取数

64             return list.get(random.nextInt(list.size()));

65         }

66     }

67

68 /**

69  * Your RandomizedSet object will be instantiated and called as such:

70  * RandomizedSet obj = new RandomizedSet();

71  * boolean param_1 = obj.insert(val);

72  * boolean param_2 = obj.remove(val);

73  * int param_3 = obj.getRandom();

74  */

map和set可不可以组合呢，想了想好像也可以，set只负责判断包含，map的存，删，随机取，都可以O（1），有待验证

巴特西

[leetcode]380. Insert Delete GetRandom O(1)设计数据结构，实现存，删，随机取的时间复杂度为O(1)

最新文章

热门文章