2017-11-10 15 views
0

에서 공통의 기록을 얻는가장 효율적인 방법은이 목록 내가 가진 두 개의 ArrayList를

ArrayList<String> l1 = new ArrayList<String>(); 
    l1.add("ABCD"); 

    l1.add("DEF"); 
    l1.add("GHI"); 
    l1.add("JKL"); 
    l1.add("MNO"); 
    l1.add("PQR"); 
    l1.add("MNO"); 

    ArrayList<String> l2 = new ArrayList<String>(); 
    l2.add("ABC"); 
    l2.add("DEF"); 
    l2.add("GHI"); 
    l2.add("PQR"); 
    l2.add("STU"); 
    l2.add("ABC"); 

데이터가 난 그냥하는이 같은 작업을 수행하는 가장 효율적인 방법이 될 것입니다 알고 싶어뿐만 아니라 수백만에서 수 .. 수

1.Solution -1-

공공의 ArrayList getCommonWords (리스트 1의 ArrayList, 의 ArrayList리스트 2)

{ 

    ArrayList<String> commonlist = new ArrayList<String>(); 
    int i = 0; 
    while (i < list1.size()) { 
     for (int j = 0; j < list2.size(); j++) { 
      if (list1.get(i) == list2.get(j)) { 
       commonlist.add(list1.get(i)); 
       break; 
      } 

     } 
     i++; 
    } 
    return commonlist; 

} 
,

솔루션 2 - 보유 함수 사용

더 효율적일 수있는 같은 .. 같은 해시 등의 다른 솔루션이 있습니까?

답변

0

여러 가지 방법이 있습니다. 속도 또는 메모리 중 어느 것이 더 중요한지 결정할 필요가 있습니다.

속도 최적화 (O (N) 런타임 복잡성, O (N) 메모리의 복잡성) :

당신은 당신의 배열의 하나의 해시 세트를 사용합니다. HashSet의 find/contains에 대한 예상 복잡도는 O (1)이고 평균은 O (b/N) 인 버킷 수 (b)에 따라 다릅니다.

{ 
    List <String> common = new ArrayList<>(); 
    HashSet<String> hs = new HashSet<>(); 
    hs.addAll(l1); // add all the items from l1 to the hashset  
    for (String s : l2) { 
    if hs.contains(s) { 
     common.add(s); 
    } 
    } 
} 

당신은 당신이 O에서 그것을 할 수있는 추가 메모리 (N의 *의 M)를 할당 할 필요가 없습니다 것입니다, 그래서 메모리를 최적화하려면 (가정 L1과 L2는 크기가 동일하지 않는 것) O (1)을 메모리에 저장합니다.

List <String> common = new ArrayList<>(); 
for (String s : l1) { 
    if l2.contains(s) { 
    common.add(s); 
    } 
} 

제안한이 해결책은 제 두 번째 해결책과 같습니다.

자바에서 개체를 비교할 때는 ==을 사용하지 않아야합니다. 객체가 동일한 참조를 갖는지 확인합니다. 대신 equals을 사용하면 콘텐츠가 동일한 지 확인합니다.