반응형
주어진 숫자와 같은 합을 가진 배열에서 원소의 쌍을 찾으십시오.
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
이 솔루션에는 세 가지 접근 방식이 있습니다.
합은 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에 대해 O (1) 인 보수 Tx를 찾을 수 있습니다.
이 방법의 전체 실행 시간은 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) 시간
- 해시의 삽입 및 조회 시간은 O (1)입니다.
- 해시와 관련하여 여분의 공간을 사용하지만 전체 시간은 O (n)입니다.
자바 솔루션. 모든 String 요소를 문자열의 ArrayList에 추가하고 목록을 반환 할 수 있습니다. 여기서 나는 그것을 인쇄하고 있습니다.
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);
}
}
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
즐겨!
파이썬 구현 :
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
의 위에)
def find_pairs(L,sum):
s = set(L)
edgeCase = sum/2
if L.count(edgeCase) ==2:
print edgeCase, edgeCase
s.remove(edgeCase)
for i in s:
diff = sum-i
if diff in s:
print i, diff
L = [2,45,7,3,5,1,8,9]
sum = 10
find_pairs(L,sum)
방법론 : a + b = c, (a, b)를 찾는 대신 a = c-b를 찾습니다.
자바 구현 : codaddict의 알고리즘 사용 :
import java.util.Hashtable;
public class Range {
public static void main(String[] args) {
// TODO Auto-generated method stub
Hashtable mapping = new Hashtable();
int a[]= {80,79,82,81,84,83,85};
int k = 160;
for (int i=0; i < a.length; i++){
mapping.put(a[i], i);
}
for (int i=0; i < a.length; i++){
if (mapping.containsKey(k - a[i]) && (Integer)mapping.get(k-a[i]) != i){
System.out.println(k-a[i]+", "+ a[i]);
}
}
}
}
산출:
81, 79
79, 81
중복 쌍 (예 : 80,80) 을 원한다면 if 조건에서 && (Integer) mapping.get (ka [i])! = i를 제거하면 좋습니다.
HackerRank 에서이 질문에 방금 참석했으며 여기에 '목표 C'솔루션이 있습니다 .
-(NSNumber*)sum:(NSArray*) a andK:(NSNumber*)k {
NSMutableDictionary *dict = [NSMutableDictionary dictionary];
long long count = 0;
for(long i=0;i<a.count;i++){
if(dict[a[i]]) {
count++;
NSLog(@"a[i]: %@, dict[array[i]]: %@", a[i], dict[a[i]]);
}
else{
NSNumber *calcNum = @(k.longLongValue-((NSNumber*)a[i]).longLongValue);
dict[calcNum] = a[i];
}
}
return @(count);
}
그것이 누군가를 돕기를 바랍니다.
이것은 루프 내에서 이진 검색 구현을 사용하여 O (n * lg n)의 구현입니다.
#include <iostream>
using namespace std;
bool *inMemory;
int pairSum(int arr[], int n, int k)
{
int count = 0;
if(n==0)
return count;
for (int i = 0; i < n; ++i)
{
int start = 0;
int end = n-1;
while(start <= end)
{
int mid = start + (end-start)/2;
if(i == mid)
break;
else if((arr[i] + arr[mid]) == k && !inMemory[i] && !inMemory[mid])
{
count++;
inMemory[i] = true;
inMemory[mid] = true;
}
else if(arr[i] + arr[mid] >= k)
{
end = mid-1;
}
else
start = mid+1;
}
}
return count;
}
int main()
{
int arr[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
inMemory = new bool[10];
for (int i = 0; i < 10; ++i)
{
inMemory[i] = false;
}
cout << pairSum(arr, 10, 11) << endl;
return 0;
}
파이썬에서
arr = [1, 2, 4, 6, 10]
diff_hash = {}
expected_sum = 3
for i in arr:
if diff_hash.has_key(i):
print i, diff_hash[i]
key = expected_sum - i
diff_hash[key] = i
Codeaddict의 멋진 솔루션. Ruby에서 버전을 구현할 자유를 얻었습니다.
def find_sum(arr,sum)
result ={}
h = Hash[arr.map {|i| [i,i]}]
arr.each { |l| result[l] = sum-l if h[sum-l] && !result[sum-l] }
result
end
중복 쌍 (1,5), (5,1)을 허용하려면 && !result[sum-l]명령 을 제거하면됩니다.
다음은 세 가지 접근 방식에 대한 Java 코드입니다.
1. Map O (n)을 사용하여 HashSet을 사용할 수도 있습니다.
2. 배열을 정렬 한 다음 BinarySearch를 사용하여 보수 O (nLog (n))를 찾습니다.
3. 전통적인 BruteForce 두 루프 O (n ^ 2)
public class PairsEqualToSum {
public static void main(String[] args) {
int a[] = {1,10,5,8,2,12,6,4};
findPairs1(a,10);
findPairs2(a,10);
findPairs3(a,10);
}
//Method1 - O(N) use a Map to insert values as keys & check for number's complement in map
static void findPairs1(int[]a, int sum){
Map<Integer, Integer> pairs = new HashMap<Integer, Integer>();
for(int i=0; i<a.length; i++){
if(pairs.containsKey(sum-a[i]))
System.out.println("("+a[i]+","+(sum-a[i])+")");
else
pairs.put(a[i], 0);
}
}
//Method2 - O(nlog(n)) using Sort
static void findPairs2(int[]a, int sum){
Arrays.sort(a);
for(int i=0; i<a.length/2; i++){
int complement = sum - a[i];
int foundAtIndex = Arrays.binarySearch(a,complement);
if(foundAtIndex >0 && foundAtIndex != i) //to avoid situation where binarySearch would find the original and not the complement like "5"
System.out.println("("+a[i]+","+(sum-a[i])+")");
}
}
//Method 3 - Brute Force O(n^2)
static void findPairs3(int[]a, int sum){
for(int i=0; i<a.length; i++){
for(int j=i; j<a.length;j++){
if(a[i]+a[j] == sum)
System.out.println("("+a[i]+","+a[j]+")");
}
}
}
}
고유 한 요소를 가진 배열을위한 Java의 간단한 프로그램 :
import java.util.*;
public class ArrayPairSum {
public static void main(String[] args) {
int []a = {2,4,7,3,5,1,8,9,5};
sumPairs(a,10);
}
public static void sumPairs(int []input, int k){
Set<Integer> set = new HashSet<Integer>();
for(int i=0;i<input.length;i++){
if(set.contains(input[i]))
System.out.println(input[i] +", "+(k-input[i]));
else
set.add(k-input[i]);
}
}
}
아래 쌍을 인쇄하기위한 간단한 Java 코드 스 니펫 :
public static void count_all_pairs_with_given_sum(int arr[], int S){
if(arr.length < 2){
return;
}
HashSet values = new HashSet(arr.length);
for(int value : arr)values.add(value);
for(int value : arr){
int difference = S - value;
if(values.contains(difference) && value<difference){
System.out.printf("(%d, %d) %n", value, difference);
}
}
}
Swift의 또 다른 솔루션 : 아이디어는 (sum-currentValue) 값을 저장하는 해시를 만들고 이것을 루프의 현재 값과 비교하는 것입니다. 복잡도는 O (n)입니다.
func findPair(list: [Int], _ sum: Int) -> [(Int, Int)]? {
var hash = Set<Int>() //save list of value of sum - item.
var dictCount = [Int: Int]() //to avoid the case A*2 = sum where we have only one A in the array
var foundKeys = Set<Int>() //to avoid duplicated pair in the result.
var result = [(Int, Int)]() //this is for the result.
for item in list {
//keep track of count of each element to avoid problem: [2, 3, 5], 10 -> result = (5,5)
if (!dictCount.keys.contains(item)) {
dictCount[item] = 1
} else {
dictCount[item] = dictCount[item]! + 1
}
//if my hash does not contain the (sum - item) value -> insert to hash.
if !hash.contains(sum-item) {
hash.insert(sum-item)
}
//check if current item is the same as another hash value or not, if yes, return the tuple.
if hash.contains(item) &&
(dictCount[item] > 1 || sum != item*2) // check if we have item*2 = sum or not.
{
if !foundKeys.contains(item) && !foundKeys.contains(sum-item) {
foundKeys.insert(item) //add to found items in order to not to add duplicated pair.
result.append((item, sum-item))
}
}
}
return result
}
//test:
let a = findPair([2,3,5,4,1,7,6,8,9,5,3,3,3,3,3,3,3,3,3], 14) //will return (8,6) and (9,5)
이것은 비트 단위 조작을 사용하여 쌍을 인쇄하고 중복을 피합니다.
public static void findSumHashMap(int[] arr, int key) {
Map<Integer, Integer> valMap = new HashMap<Integer, Integer>();
for(int i=0;i<arr.length;i++)
valMap.put(arr[i], i);
int indicesVisited = 0;
for(int i=0;i<arr.length;i++) {
if(valMap.containsKey(key - arr[i]) && valMap.get(key - arr[i]) != i) {
if(!((indicesVisited & ((1<<i) | (1<<valMap.get(key - arr[i])))) > 0)) {
int diff = key-arr[i];
System.out.println(arr[i] + " " +diff);
indicesVisited = indicesVisited | (1<<i) | (1<<valMap.get(key - arr[i]));
}
}
}
}
비트 조작을 무시하고 색인 값을 비교했습니다. 이것은 루프 반복 값보다 작습니다 (이 경우 i). 중복 쌍과 중복 배열 요소도 인쇄하지 않습니다.
public static void findSumHashMap(int[] arr, int key) {
Map<Integer, Integer> valMap = new HashMap<Integer, Integer>();
for (int i = 0; i < arr.length; i++) {
valMap.put(arr[i], i);
}
for (int i = 0; i < arr.length; i++) {
if (valMap.containsKey(key - arr[i])
&& valMap.get(key - arr[i]) != i) {
if (valMap.get(key - arr[i]) < i) {
int diff = key - arr[i];
System.out.println(arr[i] + " " + diff);
}
}
}
}
C #에서 :
int[] array = new int[] { 1, 5, 7, 2, 9, 8, 4, 3, 6 }; // given array
int sum = 10; // given sum
for (int i = 0; i <= array.Count() - 1; i++)
if (array.Contains(sum - array[i]))
Console.WriteLine("{0}, {1}", array[i], sum - array[i]);
한 가지 해결책은 이것이지만 최적은 아닙니다 (이 코드의 복잡성은 O (n ^ 2)입니다).
public class FindPairsEqualToSum {
private static int inputSum = 0;
public static List<String> findPairsForSum(int[] inputArray, int sum) {
List<String> list = new ArrayList<String>();
List<Integer> inputList = new ArrayList<Integer>();
for (int i : inputArray) {
inputList.add(i);
}
for (int i : inputArray) {
int tempInt = sum - i;
if (inputList.contains(tempInt)) {
String pair = String.valueOf(i + ", " + tempInt);
list.add(pair);
}
}
return list;
}
}
0의 쌍 합계를 찾고 k를 찾기 위해 수정할 수있는 간단한 파이썬 버전의 코드 :
def sumToK(lst):
k = 0 # <- define the k here
d = {} # build a dictionary
# build the hashmap key = val of lst, value = i
for index, val in enumerate(lst):
d[val] = index
# find the key; if a key is in the dict, and not the same index as the current key
for i, val in enumerate(lst):
if (k-val) in d and d[k-val] != i:
return True
return False
함수의 런타임 복잡도는 O (n) 및 Space : O (n)입니다.
public static int[] f (final int[] nums, int target) {
int[] r = new int[2];
r[0] = -1;
r[1] = -1;
int[] vIndex = new int[0Xfff];
for (int i = 0; i < nums.length; i++) {
int delta = 0Xff;
int gapIndex = target - nums[i] + delta;
if (vIndex[gapIndex] != 0) {
r[0] = vIndex[gapIndex];
r[1] = i + 1;
return r;
} else {
vIndex[nums[i] + delta] = i + 1;
}
}
return r;
}
https://github.com/clockzhong/findSumPairNumber
나는 시간과 메모리 공간 모두에 대해 O (m + n) 복잡성 비용으로 그것을했다. 나는 이것이 지금까지 최고의 알고리즘이라고 생각합니다.
o (n) 미만의 솔루션은 다음과 같습니다.
function(array,k)
var map = {};
for element in array
map(element) = true;
if(map(k-element))
return {k,element}
내 솔루션-Java-중복없이
public static void printAllPairSum(int[] a, int x){
System.out.printf("printAllPairSum(%s,%d)\n", Arrays.toString(a),x);
if(a==null||a.length==0){
return;
}
int length = a.length;
Map<Integer,Integer> reverseMapOfArray = new HashMap<>(length,1.0f);
for (int i = 0; i < length; i++) {
reverseMapOfArray.put(a[i], i);
}
for (int i = 0; i < length; i++) {
Integer j = reverseMapOfArray.get(x - a[i]);
if(j!=null && i<j){
System.out.printf("a[%d] + a[%d] = %d + %d = %d\n",i,j,a[i],a[j],x);
}
}
System.out.println("------------------------------");
}
목록 이해를 사용하는 Python의 솔루션
f= [[i,j] for i in list for j in list if j+i==X];
O (N 2 )
또한 (a, b) 및 (b, a)
O (n)에서 할 수 있습니다. 답변을 원할 때 알려주십시오. 정렬 등을하지 않고 배열을 한 번 순회하는 것과 관련이 있습니다. 추가의 정류를 이용하고 해시를 사용하지 않고 메모리를 낭비한다는 점도 언급해야합니다.
시스템 사용; System.Collections.Generic 사용;
/ * 조회 테이블을 사용하여 O (n) 접근 방식이 존재합니다. 이 접근 방식은 적절한 합계에 대한 후보 인 경우 쉽게 찾을 수있는 "bin"에 값을 저장하는 것입니다 (예 : O (1)).
예를 들어
배열의 각 a [k]에 대해 x-a [k] 위치의 다른 배열에 넣습니다.
[0, 1, 5, 3, 6, 9, 8, 7]이고 x = 9라고 가정합니다.
새로운 배열을 만들고
인덱스 값
9 - 0 = 9 0
9 - 1 = 8 1
9 - 5 = 4 5
9 - 3 = 6 3
9 - 6 = 3 6
9 - 9 = 0 9
9 - 8 = 1 8
9 - 7 = 2 7
그런 다음 중요한 것은 새 테이블에 인덱스가있는 값뿐입니다.
따라서 9에 도달하면 새 배열의 인덱스가 9-9 = 0인지 확인합니다. 여기에 포함 된 모든 값이 9에 추가된다는 것을 알기 때문에 1 개만 가능합니다. 하나이지만 저장해야 할 색인 값이 여러 개있을 수 있습니다).
따라서 실제로 우리가하는 일은 어레이를 한 번만 이동하면됩니다. 덧셈은 교환 적이므로 가능한 모든 결과를 얻게됩니다.
예를 들어, 6에 도달하면 새 테이블에 인덱스를 9-6 = 3으로 가져옵니다. 테이블에 해당 인덱스 값이 포함되어 있으므로 값을 알고 있습니다.
이것은 본질적으로 메모리 속도를 상쇄합니다. * /
namespace sum
{
class Program
{
static void Main(string[] args)
{
int num = 25;
int X = 10;
var arr = new List<int>();
for(int i = 0; i < num; i++) arr.Add((new Random((int)(DateTime.Now.Ticks + i*num))).Next(0, num*2));
Console.Write("["); for (int i = 0; i < num - 1; i++) Console.Write(arr[i] + ", "); Console.WriteLine(arr[arr.Count-1] + "] - " + X);
var arrbrute = new List<Tuple<int,int>>();
var arrfast = new List<Tuple<int,int>>();
for(int i = 0; i < num; i++)
for(int j = i+1; j < num; j++)
if (arr[i] + arr[j] == X)
arrbrute.Add(new Tuple<int, int>(arr[i], arr[j]));
int M = 500;
var lookup = new List<List<int>>();
for(int i = 0; i < 1000; i++) lookup.Add(new List<int>());
for(int i = 0; i < num; i++)
{
// Check and see if we have any "matches"
if (lookup[M + X - arr[i]].Count != 0)
{
foreach(var j in lookup[M + X - arr[i]])
arrfast.Add(new Tuple<int, int>(arr[i], arr[j]));
}
lookup[M + arr[i]].Add(i);
}
for(int i = 0; i < arrbrute.Count; i++)
Console.WriteLine(arrbrute[i].Item1 + " + " + arrbrute[i].Item2 + " = " + X);
Console.WriteLine("---------");
for(int i = 0; i < arrfast.Count; i++)
Console.WriteLine(arrfast[i].Item1 + " + " + arrfast[i].Item2 + " = " + X);
Console.ReadKey();
}
}
}
자바 스크립트 솔루션 :
var sample_input = [0, 1, 100, 99, 0, 10, 90, 30, 55, 33, 55, 75, 50, 51, 49, 50, 51, 49, 51];
var result = getNumbersOf(100, sample_input, true, []);
function getNumbersOf(targetNum, numbers, unique, res) {
var number = numbers.shift();
if (!numbers.length) {
return res;
}
for (var i = 0; i < numbers.length; i++) {
if ((number + numbers[i]) === targetNum) {
var result = [number, numbers[i]];
if (unique) {
if (JSON.stringify(res).indexOf(JSON.stringify(result)) < 0) {
res.push(result);
}
} else {
res.push(result);
}
numbers.splice(numbers.indexOf(numbers[i]), 1);
break;
}
}
return getNumbersOf(targetNum, numbers, unique, res);
}
int [] arr = {1,2,3,4,5,6,7,8,9,0};
var z = (a에서 arr에서 arr에서 arr에서 10-a == b new {a, b} 선택) .ToList;
반응형
'IT story' 카테고리의 다른 글
| Hive에서 테이블 파티셔닝과 버킷 팅의 차이점은 무엇입니까? (0) | 2020.07.12 |
|---|---|
| Laravel 5의 다른 컨트롤러에서 액세스 컨트롤러 방법 (0) | 2020.07.12 |
| 동적 셀 높이를 가진 UITableView의 reloadData ()로 인해 스크롤이 급증합니다. (0) | 2020.07.12 |
| XAMPP에서 phpMyAdmin으로“구성에 정의 된 controluser 연결에 실패했습니다” (0) | 2020.07.12 |
| 포지셔닝 (0) | 2020.07.12 |