go评论20阅读模式

Check the ordering of 2 different keys in LinkedHashMap in O(1)

# 问题

``````LinkedHashMap<Integer, Integer> map = new LinkedHashMap<>();
map.put(1, 1);
map.put(2, 3);
map.put(7, 4);
map.put(5, 6);
``````

``````public boolean isFirst(int key1, int key2) {
// 用于计算key1是否在key2之前的逻辑
}
``````

In a LinkedHashMap, the keys are ordered by when they were inserted into the map.

For example, consider the following map.

``````LinkedHashMap&lt;Integer,Integer&gt; map = new LinkedHashMap&lt;&gt;();
map.put(1, 1);
map.put(2, 3);
map.put(7, 4);
map.put(5, 6);
``````

So, my understanding of `LinkedHashMap` is that the keys are stored in the form a Doubly Linked List.

So, in this example, the keys would be ordered as `1&lt;-&gt;2&lt;-&gt;7&lt;-&gt;5`

Now, my requirement is this. Given 2 keys from this map, is it possible to check which one came first or last?

For example, a function like the following

``````public boolean isFirst(int key1,int key2){
// logic to compute if key1 is first
}
``````

Now, the above function can be done in O(n) easily by maintaining another map to get the order and compare it.

I want to do this operation in O(1). If it is possible, then should I maintain some other data structure to handle insertion, removal and updation of keys in the map ?

# 答案1

``````class CustomMap<K,V> extends LinkedHashMap<K,V>{
private Map<K,Integer> ord_map;
private int timestamp = 0;
CustomMap(){
super();
ord_map = new HashMap<>();
}

public V put(K key,V val){
ord_map.put(key,timestamp++);
return super.put(key,val);
}

public V remove(Object key){
ord_map.remove(key);
return super.remove(key);
}

public boolean isFirst(K key1,K key2) throws Exception{
if(!ord_map.containsKey(key1)) throw new Exception(key1 + " 不存在。");
if(!ord_map.containsKey(key2)) throw new Exception(key2 + " 不存在。");

return ord_map.get(key1) < ord_map.get(key2);
}
}
``````

``````public class Solution{
public static void main(String[] args) {
CustomMap<Integer,Integer> cmap = new CustomMap<>();
try{
cmap.put(1, 1);
cmap.put(5, 6);
cmap.put(2, 3);
cmap.put(7, 4);
System.out.println(cmap.isFirst(5,2));
cmap.remove(5);
cmap.put(5,99);
System.out.println(cmap.isFirst(5,2));
}catch(Exception e){
System.out.println(e.getMessage());
}
}
}
``````

You can create a custom class that extends `LinkedHashMap` and add the custom method `isFirst`. Internally, we keep a separate map as you already analyzed with a `timestamp` variable which acts like a timestamp for us(the second at which the key was added).

If the first key's timestamp is less than the second ones, we return `true` , else we return `false`.

Class Snippet:

``````class CustomMap&lt;K,V&gt; extends LinkedHashMap&lt;K,V&gt;{
private Map&lt;K,Integer&gt; ord_map;
private int timestamp = 0;
CustomMap(){
super();
ord_map = new HashMap&lt;&gt;();
}

public V put(K key,V val){
ord_map.put(key,timestamp++);
return super.put(key,val);
}

public V remove(Object key){
ord_map.remove(key);
return super.remove(key);
}

public boolean isFirst(K key1,K key2) throws Exception{
if(!ord_map.containsKey(key1)) throw new Exception(key1 + &quot; does not exist.&quot;);
if(!ord_map.containsKey(key2)) throw new Exception(key2 + &quot; does not exist.&quot;);

return ord_map.get(key1) &lt; ord_map.get(key2);
}
}
``````

Driver Code:

``````public class Solution{
public static void main(String[] args) {
CustomMap&lt;Integer,Integer&gt; cmap = new CustomMap&lt;&gt;();
try{
cmap.put(1, 1);
cmap.put(5, 6);
cmap.put(2, 3);
cmap.put(7, 4);
System.out.println(cmap.isFirst(5,2));
cmap.remove(5);
cmap.put(5,99);
System.out.println(cmap.isFirst(5,2));
}catch(Exception e){
System.out.println(e.getMessage());
}

}
}
``````

# 答案2

``````import java.util.*;

public class Solution {
static int index = 0;

static Map<Integer, Integer> indexMap = new HashMap<>();

static void initIndexes(LinkedHashMap<Integer, Integer> map) {
indexMap.clear();
index = 0;
map.keySet().forEach(x -> {indexMap.put(x, index++);});
}

static boolean isKeyBefore(int key1, int key2) {
return indexMap.getOrDefault(key1, Integer.MAX_VALUE) <
indexMap.getOrDefault(key2, -1);
}

public static void main(String []args) {
map.put(1, 1);
map.put(2, 3);
map.put(7, 4);
map.put(5, 6);

initIndexes(map);

System.out.println(indexMap);

System.out.println(isKeyBefore(2, 5)); // true
System.out.println(isKeyBefore(7, 1)); // false
System.out.println(isKeyBefore(5, 3)); // key2 is not in the indexMap
System.out.println(isKeyBefore(4, 2)); // key1 is not in the indexMap
System.out.println(isKeyBefore(6, 8)); // both keys are not in the indexMap

}
}
``````

There could be a solution based on HashMap for indexes, but it has O(N) complexity both in time and memory to populate the index map.

``````import java.util.*;
public class Solution {
static int index = 0;
static Map&lt;Integer, Integer&gt; indexMap = new HashMap&lt;&gt;();
static void initIndexes(LinkedHashMap&lt;Integer, Integer&gt; map) {
indexMap.clear();
index = 0;
map.keySet().forEach(x -&gt; {indexMap.put(x, index++);});
}
static boolean isKeyBefore(int key1, int key2) {
return indexMap.getOrDefault(key1, Integer.MAX_VALUE) &lt;
indexMap.getOrDefault(key2, -1);
}
public static void main(String []args) {
map.put(1, 1);
map.put(2, 3);
map.put(7, 4);
map.put(5, 6);
initIndexes(map);
System.out.println(indexMap);
System.out.println(isKeyBefore(2, 5)); // true
System.out.println(isKeyBefore(7, 1)); // false
System.out.println(isKeyBefore(5, 3)); // key2 is not in the indexMap
System.out.println(isKeyBefore(4, 2)); // key1 is not in the indexMap
System.out.println(isKeyBefore(6, 8)); // both keys are not in the indexMap
}
}
``````

• 本文由 发表于 2020年7月23日 02:11:20
• 转载请务必保留本文链接：https://go.coder-hub.com/63040638.html
• algorithm
• java

go 13

go 16

go 19

go 18