조합 행

Question

값의 조합이 존재하는지 여부를 확인하고 싶습니다. 아래 코드는 잘 작동하지만 비효율적입니다. 나는이 문제의 좋은 해결책을 찾고있다.

public static void main(String args[]) { 

    Integer data[] = { 
      1, 2, 5, 1, 9, 3, 5, 3, 2 
    }; 

    Integer combination[] = { 
      1, 3 ,2 
    }; 

    System.out.println("Result: " + combinations(data, combination)); 
} 


public static boolean combinations(Integer dataset[], Integer combination[]) { 

    boolean results[] = new boolean[combination.length]; 

    Integer count = 0; 
    for (Integer comb : combination) { 

     for (Integer data : dataset) { 
      if (data.equals(comb)) { 
       results[count++] = true; 
       break; 
      } 
     } 

    } 

    for (Boolean result : results) { 
     if (!result) { 
      return false; 
     } 
    } 
    return true; 
} 

강한 텍스트

Answer 1

는 "필적"구현 정수로 구성 코드, 나는 당신이 그것을 악용 제안하고 TreeSet의를 구성하고 그것으로 모든 데이터를 추가합니다. 그런 다음 contains()를 실행하여 TreeSet에 요소가 있는지 여부를 확인할 수 있습니다. TreeSet은 추가, 삭제 및 포함 할 때마다 log (n) 비용을 보장합니다. 모든 원소 (n)를 더하면 n log (n)가 발생합니다. 'm'요소가 있으면 찾기는 log (n)입니다.

Answer 2

정렬 복잡도 nlog (n)에있는 데이터 세트 세트. (빠른 또는 병합 정렬 어쩌면?) 그런 다음 데이터 집합에 대해 조합 배열의 모든 구성원에 대해 이진 검색을 실행합니다. 이진 검색 복잡도 로그 (n). 조합 배열의 모든 구성원에 대해 이렇게하면 복잡성은 nlog (n)가됩니다.

nlog (n) + nlog (n) = 2nlog (n) 이는 O (nlogn)이다. 이렇게하면 실적이 향상됩니다.

---

데이터 이후

public static boolean combinations(Integer dataset[], Integer combination[]) { 

sort(dataset); // quick or insertion sort, nlogn 


for (Integer comb : combination) { // n 

    if (!binarysearch(dataset, comb)) //logn 
     return false; 
} //n*logn = nlogn 

return true;} //2nlogn = O(nlogn) 

Answer 3

배열에서 ArrayList로 변경하고 containsAll 메서드를 사용할 수 있습니다. 충분히 효율적인지는 모르지만 코드를 더 짧게 만들 것입니다. 당신은 단지 조합은 데이터 집합의 부분 집합인지 확인하려면 같은

public static void main(String args[]) { 
    Integer data[] = {1, 2, 5, 1, 9, 3, 5, 3, 2}; 
    Integer combination[] = {1,3 ,2}; 
    System.out.println("Result: " + combinations(data, combination)); 
} 
public static boolean combinations(Integer dataset[], Integer combination[]) { 
    List<Integer> data = Arrays.asList(dataset); 
    List<Integer> comb = Arrays.asList(combination); 
    return data.containsAll(comb); 
} 

Answer 4

가 보이는 ... 순서가있는이 데이터 세트에 표시하는 것은 중요하지 않습니다. 그 맞습니까?

데이터 세트의 크기는 어느 정도입니까? 데이터 세트가 필요할 때마다 생성되거나 전체적으로 유지 관리됩니까?

데이터 세트가 크고 전체적으로 유지 관리되면 정렬 된 상태로 유지 관리 할 수 ​​있는지 쉽게 검색 할 수 있습니다.

for (Integer comb : combination) { 
    if (Arrays.binarySearch(dataset, comb) < 0) 
     return false; //If any element is not found, return false 
    } 
} 
return true; 

조합을 정렬 된 상태로 유지할 수 있다면 더 최적화 할 수 있습니다. 당신이 정렬 된 배열을 유지할 수없는 경우에도

int loc = 0; 
for (Integer comb : combination) { 
    loc = Arrays.binarySearch(dataset, loc, data.length, comb); 
    //Since both are sorted, u can be sure that next element will be 
    //after previous element match 
    if (loc < 0) 
     return false; 
    } 
} 
return true; 

는 유 할 수있는 하나의 최적화는 부울 배열 및 하단에 대한 루프를 제거하는 것입니다. 코드가 작동하고 당신이 더 더 효율적인 솔루션을 찾고 있다면 알고리즘

boolean isMatch = false; 
for (Integer comb : combination) { 
    //We will be here in two condition - 
    // 1. first iteration or previous element was found in dataset. 
    // 2. Just set to false to check next element. Reset the flag 
    boolean isMatch = false; 
    for (Integer data : dataset) { 
     if (data.equals(comb)) { 
      //match found for the current combination element 
      isMatch = true; 
      break; 
     } 
    } 
    //This mean one of the combination element is not there. Break out. 
    if (!isMatch) break; 
} 
return isMatch;