[algorithm] 합이 주어진 숫자와 같은 배열에서 한 쌍의 요소 찾기
n 개의 정수 배열과 숫자 X가 주어지면 합이 X와 같은 모든 고유 한 요소 쌍 (a, b)을 찾습니다.
다음은 내 솔루션이며 O (nLog (n) + n)이지만 최적인지 여부는 확실하지 않습니다.
int main(void)
{
int arr [10] = {1,2,3,4,5,6,7,8,9,0};
findpair(arr, 10, 7);
}
void findpair(int arr[], int len, int sum)
{
std::sort(arr, arr+len);
int i = 0;
int j = len -1;
while( i < j){
while((arr[i] + arr[j]) <= sum && i < j)
{
if((arr[i] + arr[j]) == sum)
cout << "(" << arr[i] << "," << arr[j] << ")" << endl;
i++;
}
j--;
while((arr[i] + arr[j]) >= sum && i < j)
{
if((arr[i] + arr[j]) == sum)
cout << "(" << arr[i] << "," << arr[j] << ")" << endl;
j--;
}
}
}
답변
# Let arr be the given array.
# And K be the give sum
for i=0 to arr.length - 1 do
hash(arr[i]) = i // key is the element and value is its index.
end-for
for i=0 to arr.length - 1 do
if hash(K - arr[i]) != i // if Kth element exists and it's different then we found a pair
print "pair i , hash(K - arr[i]) has sum K"
end-if
end-for
답변
이 솔루션에는 3 가지 접근 방식이 있습니다.
합계를 T로, n을 배열의 크기로 설정합니다.
접근 방식 1 :
이를 수행하는 순진한 방법은 모든 조합을 확인하는 것입니다 (n 선택 2). 이 철저한 검색은 O (n 2 )입니다.
접근 방식 2 :
더 나은 방법은 배열을 정렬하는 것입니다. 이것은 O (n log n)를 취합니다.
그런 다음 배열 A의 각 x에 대해 이진 검색을 사용하여 Tx를 찾습니다. O (nlogn)이 필요합니다.
따라서 전체 검색은 O (n log n)입니다.
접근법 3 :
가장 좋은 방법은 모든 요소를 정렬없이 해시 테이블에 삽입하는 것입니다. 이것은 O (n)을 상수 시간 삽입으로 사용합니다.
그런 다음 모든 x에 대해 그 보수 Tx, 즉 O (1)을 찾을 수 있습니다.
이 접근 방식의 전체 실행 시간은 O (n)입니다.
여기에서
자세한 내용을 참조 할 수 있습니다 . 감사합니다.
답변
Java로 구현 : codaddict의 알고리즘 사용 (약간 다를 수 있음)
import java.util.HashMap;
public class ArrayPairSum {
public static void main(String[] args) {
int []a = {2,45,7,3,5,1,8,9};
printSumPairs(a,10);
}
public static void printSumPairs(int []input, int k){
Map<Integer, Integer> pairs = new HashMap<Integer, Integer>();
for(int i=0;i<input.length;i++){
if(pairs.containsKey(input[i]))
System.out.println(input[i] +", "+ pairs.get(input[i]));
else
pairs.put(k-input[i], input[i]);
}
}
}
입력 = {2,45,7,3,5,1,8,9}및 합계가10
출력 쌍 :
3,7
8,2
9,1
솔루션에 대한 몇 가지 참고 사항 :
- 배열-> O (n) 시간을 한 번만 반복합니다.
- Hash의 삽입 및 조회 시간은 O (1)입니다.
- 전체 시간은 O (n)이지만 해시 측면에서 추가 공간을 사용합니다.
답변
자바의 솔루션. 문자열의 ArrayList에 모든 String 요소를 추가하고 목록을 반환 할 수 있습니다. 여기서 나는 그것을 인쇄하고 있습니다.
void numberPairsForSum(int[] array, int sum) {
HashSet<Integer> set = new HashSet<Integer>();
for (int num : array) {
if (set.contains(sum - num)) {
String s = num + ", " + (sum - num) + " add up to " + sum;
System.out.println(s);
}
set.add(num);
}
}
답변
Python 구현 :
import itertools
list = [1, 1, 2, 3, 4, 5,]
uniquelist = set(list)
targetsum = 5
for n in itertools.combinations(uniquelist, 2):
if n[0] + n[1] == targetsum:
print str(n[0]) + " + " + str(n[1])
산출:
1 + 4
2 + 3
답변
C ++ 11, 런타임 복잡성 O (n) :
#include <vector>
#include <unordered_map>
#include <utility>
std::vector<std::pair<int, int>> FindPairsForSum(
const std::vector<int>& data, const int& sum)
{
std::unordered_map<int, size_t> umap;
std::vector<std::pair<int, int>> result;
for (size_t i = 0; i < data.size(); ++i)
{
if (0 < umap.count(sum - data[i]))
{
size_t j = umap[sum - data[i]];
result.push_back({data[i], data[j]});
}
else
{
umap[data[i]] = i;
}
}
return result;
}
답변
여기에 솔루션 마녀가 중복 항목을 고려합니다. 자바 스크립트로 작성되었으며 배열이 정렬되었다고 가정합니다. 이 솔루션은 O (n) 시간에 실행되며 변수 외에 추가 메모리를 사용하지 않습니다.
var count_pairs = function(_arr,x) {
if(!x) x = 0;
var pairs = 0;
var i = 0;
var k = _arr.length-1;
if((k+1)<2) return pairs;
var halfX = x/2;
while(i<k) {
var curK = _arr[k];
var curI = _arr[i];
var pairsThisLoop = 0;
if(curK+curI==x) {
// if midpoint and equal find combinations
if(curK==curI) {
var comb = 1;
while(--k>=i) pairs+=(comb++);
break;
}
// count pair and k duplicates
pairsThisLoop++;
while(_arr[--k]==curK) pairsThisLoop++;
// add k side pairs to running total for every i side pair found
pairs+=pairsThisLoop;
while(_arr[++i]==curI) pairs+=pairsThisLoop;
} else {
// if we are at a mid point
if(curK==curI) break;
var distK = Math.abs(halfX-curK);
var distI = Math.abs(halfX-curI);
if(distI > distK) while(_arr[++i]==curI);
else while(_arr[--k]==curK);
}
}
return pairs;
}
대기업 인터뷰에서이 문제를 해결했습니다. 그들은 그것을 가져 갔지만 나는 아닙니다. 그래서 여기 모두를위한 것입니다.
어레이의 양쪽에서 시작하여 천천히 안쪽으로 작업하여 중복 항목이있는 경우 개수를 확인합니다.
쌍만 계산하지만 다시 작업 할 수 있습니다.
- 쌍을 찾아
- 쌍 찾기 <x
- 쌍 찾기> x
즐겨!
