두 개의 배열을 비교하고 정렬되지 않은 배열을 비교하고 C++을 사용하여 동일한 값을 갖는지 확인하는 가장 좋은 방법은 무엇입니까? O (nlogn)의 솔루션을 찾았지만 이에 대한 O (n) 솔루션이 있습니까? 어떻게, 그래?두 개의 정수 배열을 비교하여 같은 값을 가지고 있는지 확인하십시오.
저는 이것이 대학의 질문이 아니라는 것을 알려 드리겠습니다. ACM 문제 해결을 알고 싶습니다.
감사합니다.
값은 무엇이며 얼마만큼의 메모리를 사용 하느냐에 달려 있습니다. 두 이제
int array1[N];
int array2[N];
//get the values into array1 and 2 from somehwere
char count[c]{0};
for(size_t i=0; i<N; i++) {
count[array1[i]]++;
count[array2[i]]++;
}
: 범위 독특한 정수 X를 포함하는 배열에 대한 O (n)이 솔루션에서 0 < = X < C, 당신은 보조 배열 char count[c]를 사용하고 같은 것을 할 수 count의 모든 요소가 0 또는 2 인 경우에만 배열이 동일하게됩니다. 동일한 루프를 다시 실행하여이 시간 (count[array1[i]] (및 과 동일))을 검사하여 O (n) 동일한 기술을 다른 몇 가지 시나리오에 적용 할 수 있습니다. 예를 들어 값이 고유하지 않은 경우 두 개의 개별 배열로 계산 한 다음 두 개수가 동일한 지 확인해야합니다. 그러나 가능한 값의 수가 너무 많은 경우 작업이 O (n log n) 인 트리와 같은 다른 구조에 정보를 저장해야합니다 ('x는 배열에 포함됨'). 네가 시작한 곳으로 돌아 간다.
답장을 보내 주셔서 감사합니다. 그러나 값이 범위에 묶이지 않은 경우 예를 들어 크기가 20이고 23967 인 배열을 가질 수 있습니다! – Mohammad
음, 다른 문제는 (특히 20과 같은 작은 n의 경우), O (...)에 대해서는별로 신경 쓰지 않지만 필요한 절대 시간은 중요하다는 것입니다. 선 인자, 즉 a와 b는 \ * n과 b \ * n \ * log (n)으로 접근 방식에 따라 크게 다를 수 있으므로 일반적으로 작아 진 배열을 다루는 경우 가장 적합한 방법을 찾아야합니다. 절대 시간의 관점에서 전형적인 * 크기는 가장 좋은 점근 적 행동을하는 것보다 크다. – Oguk
내가 누락되었지만 값의 범위가 있어도 이것이 나에게 유효하지 않은 것으로 보입니다. 예를 들어, array1 = [1, 1, 2, 2]이고 array2 = [3, 3, 4, 4]가 [0, 2, 2, 2, 2]로 계산되지 않는다면? 귀하의 솔루션을 읽었을 때,이 두 배열을 동일하게 표시합니다. 편집 : 나는 독특한 단어를 놓친 ... –
동일한 길이의 배열입니까? 배열 내의 요소 순서가 중요합니까? 예를 들어 [9, 2, 5]와 [5, 2, 9]가 같습니까? –
나는'O (n lg n)'이 당신이 할 수있는 최선이라고 확신합니다. – o11c
@ o11c 그래, 그가 캠에 대한 다른 가정을하지 않는 한, 나는 네가 옳다고 믿는다. – IdeaHat