|
1 | 1 | classFirstUnique { |
2 | | -Map<Integer,Integer>valToCount; |
3 | | -Map<Integer,Integer>countToVal; |
4 | | -intcount; |
5 | | -intlowest; |
| 2 | +Nodehead; |
| 3 | +Nodetail; |
| 4 | +Map<Integer,Node>map; |
| 5 | +intMX_VAL =Integer.MAX_VALUE; |
| 6 | +intMN_VAL =Integer.MIN_VALUE; |
6 | 7 | publicFirstUnique(int[]nums) { |
7 | | -valToCount =newHashMap<>(); |
8 | | -countToVal =newHashMap<>(); |
9 | | -count =0; |
10 | | -lowest =0; |
| 8 | +map =newHashMap<>(); |
| 9 | +head =newNode(MN_VAL); |
| 10 | +tail =newNode(MX_VAL); |
| 11 | +head.next =tail; |
| 12 | +tail.prev =head; |
11 | 13 | for (intnum :nums) { |
12 | 14 | add(num); |
13 | 15 | } |
14 | 16 | } |
15 | 17 |
|
16 | 18 | publicintshowFirstUnique() { |
17 | | -while (lowest <count &&countToVal.get(lowest) == -1) { |
18 | | -lowest++; |
19 | | - } |
20 | | -if (lowest ==count) { |
21 | | -lowest--; |
22 | | -return -1; |
23 | | - } |
24 | | -returncountToVal.get(lowest); |
| 19 | +returnhead.next.val ==MX_VAL ? -1 :head.next.val; |
25 | 20 | } |
26 | 21 |
|
27 | 22 | publicvoidadd(intvalue) { |
28 | | -if (valToCount.containsKey(value)) { |
29 | | -intidx =valToCount.get(value); |
30 | | -countToVal.put(idx, -1); |
| 23 | +if (map.containsKey(value)) { |
| 24 | +if (map.get(value) !=null) { |
| 25 | +remove(map.get(value)); |
| 26 | +map.put(value,null); |
| 27 | + } |
31 | 28 | } |
32 | 29 | else { |
33 | | -valToCount.put(value,count++); |
34 | | -countToVal.put(valToCount.get(value),value); |
| 30 | +NodenewNode =newNode(value); |
| 31 | +map.put(value,newNode); |
| 32 | +newNode.prev =tail.prev; |
| 33 | +tail.prev.next =newNode; |
| 34 | +newNode.next =tail; |
| 35 | +tail.prev =newNode; |
35 | 36 | } |
36 | 37 | } |
| 38 | + |
| 39 | +privatevoidremove(Nodenode) { |
| 40 | +Nodeprev =node.prev; |
| 41 | +Nodenext =node.next; |
| 42 | +prev.next =next; |
| 43 | +next.prev =prev; |
| 44 | + } |
| 45 | +} |
| 46 | + |
| 47 | +classNode { |
| 48 | +intval; |
| 49 | +Nodenext; |
| 50 | +Nodeprev; |
| 51 | + |
| 52 | +publicNode(intval) { |
| 53 | +this.val =val; |
| 54 | + } |
37 | 55 | } |
38 | 56 |
|
39 | 57 | /** |
|