Interview 150
Insert Delete GetRandom O(1)
- Problem
- LC 380
- File
- interview150_LC380InsertDeleteGetRandom.java
- Path
- pkg5leetcode/interview150/interview150_LC380InsertDeleteGetRandom.java
- Package
- pkg5leetcode.interview150
- Command
- java pkg5leetcode/interview150/interview150_LC380InsertDeleteGetRandom.java
There is no in-browser runner. This is the file from the curriculum, unchanged.
1package pkg5leetcode.interview150;2 3/** LC 380 Insert Delete GetRandom O(1) */4import java.util.*;5 6public class interview150_LC380InsertDeleteGetRandom {7 static class RandomizedSet {8 List<Integer> list = new ArrayList<>();9 Map<Integer,Integer> idx = new HashMap<>();10 boolean insert(int val) { if (idx.containsKey(val)) return false; idx.put(val, list.size()); list.add(val); return true; }11 boolean remove(int val) {12 if (!idx.containsKey(val)) return false;13 int i = idx.remove(val), last = list.remove(list.size()-1);14 if (val != last) { idx.put(last, i); list.set(i, last); }15 return true;16 }17 int getRandom() { return list.get(new Random().nextInt(list.size())); }18 }19 20 public static void main(String[] args) {21 RandomizedSet set = new RandomizedSet();22 System.out.println(set.insert(1));23 System.out.println(set.remove(2));24 System.out.println(set.insert(2));25 System.out.println(set.getRandom());26 }27}