두 개의 배열이 주어지면 두 배열에 공통적 인 최대 요소를 찾는 방법은 무엇입니까?두 배열에서 공통적 인 최대 요소를 찾으십니까?
두 배열 (n log n)을 정렬 한 다음 일치하는 항목이 발견 될 때까지 다른 배열의 한 정렬 된 배열 (더 큰 배열에서 시작)의 모든 요소에 대한 이진 검색을 수행하려고합니다.
예 :
a = [1,2,5,4,3]
b = [9,8,3]
Maximum common element in these array is 3
우리는 N 로그 n보다 더 잘 할 수 있습니까?
일부 추가 공간을 사용하면 1 배열에서 해시 한 다음 다른 배열의 각 요소에 true를 반환하는 가장 큰 값을 포함하는 내용을 포함 할 수 있습니다. O (n)이 될 것입니다.
그냥 저를 때려주십시오. 물론 해시가 고유하지 않은 경우 시간 복잡도가 약간 더 높을 수 있습니다 (해시 일치가 실제 일치인지 확인). 해시가 고유하면 O (n) 스토리지 비용이 발생합니다. – Patrick87
O(N) 공간을 사용할 수 있습니다.
첫 번째 배열을 통해 모든 요소를 HashTable에 배치하십시오. 이것은 O(N)
입니다. 그런 다음 현재 최대 값을 추적하고 요소가 HashTable에 있는지 확인하는 두 번째 배열을 살펴보십시오. 이것은 O(N)입니다. 그것은 특정 언어의 다양한 작업의 시간 복잡성에 따라 다르지만, 어떻게 배열에서 세트를 만드는 방법에 대해
public static int getMaxCommon(int[] a, int[] b){
Set<Integer> firstArray = new HashSet<Integer>(Arrays.asList(a));
int currentMax = Integer.MIN_VALUE;
for(Integer n:b){
if(firstArray.contains(n)){
if(currentMax < n){
currentMax = n
}
}
}
return currentMax;
}
: 그래서 총 런타임은 O(N) 및 Java에서 HashTable
예를 들어 O(N) 여분의 공간입니다 두 세트의 교차에서 최대 값을 찾는 것? 파이썬에서 연산을 수행하는 시간이 복잡해지면 집합 할당을위한 O (n), 교차점의 O (n), 최대 값을 찾는 O (n)이 평균적으로 있습니다. 그러므로 평균적인 경우는 O (n)입니다.
그러나! 최악의 경우 집합 교차점의 최악의 경우 복잡성 때문에 O (len (a) * len (b)) -> O (n^2)가됩니다. 당신이 관심이 있다면 여기
는 이미 배열에있을 것입니다 숫자의 범위를 알고 있다면, 당신은 종류의 계산 수행 할 수 있습니다, 그리고 당신이 원하는 것처럼 이진 검색을 수행합니다. 이것은 O (n) 런타임을 산출합니다.
의사 코드 :
sort list1 in descending order
sort list2 in descending order
item *p1 = list1
item *p2 = list2
while ((*p1 != *p2) && (haven't hit the end of either list))
if (*p1 > *p2)
++p1;
else
++p2;
// here, either we have *p1 == *p2, or we hit the end of one of the lists
if (*p1 == *p2)
return *p1;
return NOT_FOUND;
'sort list1 in descending order'는'O (N)'연산인가요? 그렇게 생각하지 않습니다.'O (N)'정렬 알고리즘을 찾지 못한 경우 – Cratylus
새로운 정렬 알고리즘을 발견하지 못하면 Not not. O (N log n)은 O (N log n) 스캔을위한 정렬 + O (N log n) 전체에 대한 것입니다. 나는 당신이 처음에리스트의 순서에 대해 특정 가정을 할 수 없다면 더 잘할 수 없다고 확신합니다. – twalberg
OP는 정렬 작업을 사전 처리 단계로 사용할 수 있음을 이미 알고 있습니다. OP는 'O (N)'접근 방식에 관한 것입니다. 만약 당신이 그것을 분명히 정렬하지 않는다면 새로운 정렬 알고리즘을 고안하는 것에 대한 제 의견을 말할 수 있습니다. – Cratylus
아니 완벽하지만 간단한 해결책, O (LEN (배열 1) + 렌 (배열 2))
import sys
def find_max_in_common(array1, array2):
array1 = set(array1)
array2 = set(array2)
item_lookup = {}
for item in array1:
item_lookup[item] = True
max_item = -sys.maxsize
intersection = False
for item in array2:
if not item_lookup.get(item, None):
continue
else:
intersection = True
if item > max_item:
max_item = item
return None if not intersection else max_item
하지,하지만에서 마지막 단계는 너무 작은 값을 찾으면 조기 검색을 사용하여 선형 검색을 수행하는 것이 이진 검색보다 빠를 가능성이 높습니다. 당신이 찾고있는 값이 당신이 찾은 마지막 값보다 작기 때문에 당신이 처음부터 끝내지 않은 지점부터 다시 시작할 수 있습니다. 따라서 검색에 소비되는 총 시간은 O ("다른 배열"의 크기)이며, "하나의 정렬 된 배열"의 요소간에 불균등하게 나눕니다. 보간 검색 등을 수행 할 수도 있습니다. –