英文:
Check the ordering of 2 different keys in LinkedHashMap in O(1)
问题
在LinkedHashMap中,键的顺序是根据它们插入到映射中的时间来排序的。
例如,考虑以下映射。
LinkedHashMap<Integer, Integer> map = new LinkedHashMap<>();
map.put(1, 1);
map.put(2, 3);
map.put(7, 4);
map.put(5, 6);
所以,我对LinkedHashMap
的理解是,键以双向链表的形式存储。
因此,在这个示例中,键的顺序将是1<->2<->7<->5
。
现在,我的需求是这样的。给定来自这个映射的两个键,是否可以检查哪一个先插入,哪一个后插入?
例如,一个像下面这样的函数:
public boolean isFirst(int key1, int key2) {
// 用于计算key1是否在key2之前的逻辑
}
现在,可以轻松地通过维护另一个映射以获取顺序并进行比较来在O(n)中完成上述函数。
我想在O(1)中执行此操作。如果可能的话,我应该维护一些其他数据结构来处理映射中键的插入、删除和更新吗?
英文:
In a LinkedHashMap, the keys are ordered by when they were inserted into the map.
For example, consider the following map.
LinkedHashMap<Integer,Integer> map = new LinkedHashMap<>();
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<->2<->7<->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
得分: 2
你可以创建一个自定义类,它扩展了 LinkedHashMap
,并添加了自定义方法 isFirst
。在内部,我们保留了一个单独的映射,就像你已经分析过的那样,其中有一个 timestamp
变量,它充当了时间戳,表示键添加的秒数。
如果第一个键的时间戳小于第二个键的时间戳,我们返回 true
,否则返回 false
。
类片段:
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<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 + " does not exist.");
if(!ord_map.containsKey(key2)) throw new Exception(key2 + " does not exist.");
return ord_map.get(key1) < ord_map.get(key2);
}
}
Driver Code:
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());
}
}
}
答案2
得分: 1
以下是翻译好的部分:
有一种基于HashMap的索引解决方案,但在填充索引映射时,它的时间和内存复杂度都是O(N)。
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) {
LinkedHashMap<Integer,Integer> map = new LinkedHashMap<>();
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<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) {
LinkedHashMap<Integer,Integer> map = new LinkedHashMap<>();
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
}
}
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库,让每个人都能够通过互相帮助和分享经验来进步。
评论