Maping 키 값 시간 복잡도가

Question

을 중요한 I는 다음과 같이 두 개의 배열을 가지고 ..

Long key1= 1l; Long key2= 2l; Long key3= 3l; Long key4= 4l; 
Long key5= 2l; Long key6= 3l; Long key7= 1l; Long key8= 2l; 
Long key9= 4l; 

MyObject ob1= new MyObject(1l);  MyObject ob2= new MyObject(3l);  MyObject ob3= new MyObject(2l); 
MyObject ob4= new MyObject(1l);  MyObject ob5= new MyObject(4l);  MyObject ob6= new MyObject(3l); 
MyObject ob7= new MyObject(4l);  MyObject ob8= new MyObject(2l);  MyObject ob9= new MyObject(1l); 

Long[] keys= new Long[]{key1,key2,key3,key4,key5,key5,key7,key8,key9}; 
MyObject[] objects= new MyObject[]{ob1,ob2,ob3,ob4,ob5,ob6,ob7,ob8,ob9}; 

내가 키 객체를 매핑 할. 따라서 각 키에는 연관된 객체 목록이 있습니다. 나는이 방법으로 성공입니다

,

('B' "상자, Ball..etc"자세히 이하 내 문제는 "애플, 도끼, 에어로 '지도'A '... 같은 것입니다) 내가하고있는 일이지만 문제는 O (n * n) 이상인 시간 복잡도입니다 (키를 가져 와서 각 객체 키와 비교합니다.).

시간 복잡성이 o (n * n) 미만인 사람이이 작업을하도록 도와 줄 수 있습니까? 시간 복잡성 문제.

JDK 1.6 사용.

My Program: 


import java.util.ArrayList; 
import java.util.HashMap; 
import java.util.List; 
import java.util.Map; 

public class Bar 
    { 
Long key1= 1l; Long key2= 2l; Long key3= 3l; Long key4= 4l; 
Long key5= 2l; Long key6= 3l; Long key7= 1l; Long key8= 2l; 
Long key9= 4l; 

MyObject ob1= new MyObject(1l);  MyObject ob2= new MyObject(3l);  MyObject ob3= new MyObject(2l); 
MyObject ob4= new MyObject(1l);  MyObject ob5= new MyObject(4l);  MyObject ob6= new MyObject(3l); 
MyObject ob7= new MyObject(4l);  MyObject ob8= new MyObject(2l);  MyObject ob9= new MyObject(1l); 

Long[] keys= new Long[]{key1,key2,key3,key4,key5,key5,key7,key8,key9}; 
MyObject[] objects= new MyObject[]{ob1,ob2,ob3,ob4,ob5,ob6,ob7,ob8,ob9}; 


public void mapper() 
{ 
    Map<Long, List<MyObject>> keyToObjectMap= new HashMap<Long,List<MyObject>>(); 

    for(int i=0;i<keys.length;i++) 
    { 
     for(MyObject object:objects) 
     { 
      if(keyToObjectMap.containsKey(keys[i])) 
      { 
       if(keys[i].equals(object.getKey())) 
       { 
        List<MyObject> objs= keyToObjectMap.get(keys[i]); 
        if(!objs.contains(object)) 
        { 
         objs.add(object); 
        } 
        keyToObjectMap.put(keys[i], objs); 
       } 
      } 
      else if(keys[i].equals(object.getKey())) 
      { 
       List<MyObject> objs= new ArrayList<MyObject>(); 
       objs.add(object); 
       keyToObjectMap.put(keys[i], objs); 
      }     
     } 
    }  
} 

public static void main(String[] args) 
{ 
    Bar b= new Bar(); 
    b.mapper(); 
} 

    } 



class MyObject 
{ 
Long key; 
String desc="description"; 

MyObject(Long key) 
{ 
    this.key=key; 
} 

public Long getKey(){ 
    return key; 
} 
} 

Answer 1

검색 성능이 중요한 경우 목록의 해시 대신 해시의 해시를 사용해야합니다.

외부 해시에는 일정한 비용이 있으므로 o (nn)이 아닙니다.

Answer 2

O (n)에서 이와 같이 할 수 있습니다.

Map<Long, Set<MyObject>> keyToObjectMap = new HashMap<>(); 
for (MyObject o : objects) { 
    Set<MyObject> set = ketToObjectMap.get(o.getKey()); 
    if (set == null) 
     keyToObjectMap.put(o.getKey(), set = new HashSet<>()); 
    set.add(o); 
} 

자바 8에서는

Map<Long, Set<MyObject>> map = objects.stream() 
       .collect(Collectors.groupingBy(MyObject::getKey, Collectors.toSet()));