두 어레이 간의 교차점을 새 어레이로 만들려면 어떻게 해야 합니까?
나는 여러 가지 상황에서 이 문제에 여러 번 직면했다.C 또는 Java에 익숙하지만 모든 프로그래밍 언어에 일반적입니다.
2개의 어레이(또는 컬렉션)에 대해 생각해 보겠습니다.
char[] A = {'a', 'b', 'c', 'd'};
char[] B = {'c', 'd', 'e', 'f'};
두 어레이 간의 공통 요소를 새로운 어레이로 가져오려면 어떻게 해야 합니까?는 "A" B"입니다.char[] c = {'c', 'd'}.
대형 어레이의 경우 실행 시간이 (A의 길이와 B의 길이)만큼 늘어나는 다른 어레이의 반복을 피하고 싶습니다.
각 어레이에서 공통 요소를 얻기 위해 단일 경로를 사용할 수 있는 방법이 있습니까?
foreach element e in array A
insert e into hash table H
foreach element e in array B
if H contains e
print e
은 " " " 입니다.O(N)O(N)우주에서.
추가 공간을 피하기 위해 정렬 기반 접근 방식을 사용할 수 있습니다.
효율성의 하한은 O(n)입니다. 최소한 모든 요소를 읽어야 합니다.다음으로 몇 가지 특징이 있습니다.
가장 단순한 접근법
어레이 2의 어레이 1에서 모든 요소를 검색합니다.시간 복잡도 O(n^2)
정렬 접근법
배열 1개만 정렬한 다음 이진 검색을 사용하여 배열 2에서 요소를 검색해야 합니다.시간 복잡도: O(nlogn), 검색 O(n * logn) = O(nlogn), 총 O(nlogn).
해시 어프로치
어레이 1 요소에서 해시 테이블을 만듭니다.해시 테이블의 두 번째 테이블에서 요소를 검색합니다.시간 복잡도는 해시 함수에 따라 달라집니다.최적의 경우 검색용 O(1)를 얻을 수 있지만(모든 요소의 해시 값이 서로 다름), 최악의 경우 O(n)를 얻을 수 있습니다(모든 요소의 해시 값이 동일함).총 시간 복잡도: O(n^x). 여기서 x는 해시 함수 효율의 계수(1과 2)입니다.
일부 해시 함수는 충돌 없이 테이블을 구축할 수 있습니다.그러나 빌딩은 모든 요소에 대해 O(1) 시간이 더 이상 걸리지 않습니다.대부분의 경우 O(1)이지만 테이블이 꽉 찼거나 충돌이 발생한 경우 테이블을 재플래시해야 합니다(O(n) 시간이 걸립니다).이것은 그다지 자주 발생하는 것이 아니고, 클린 애드보다 훨씬 적은 빈도로 발생합니다.따라서 상각후 시간의 복잡도는 O(1)이다.대부분의 추가에 O(1) 시간이 걸리는 한 일부 추가에 O(n) 시간이 걸리는 것은 상관없습니다.
단, 극단적인 경우에는 테이블이 삽입될 때마다 다시 작성되어야 하므로 엄격한 시간 복잡도는 O(n^2)가 됩니다.
일부 언어에는 사용자가 원하는 대로 실행하는 방법이 몇 가지 있는데, 이러한 구현에 대해 검토해 보셨습니까?
PHP - array_intersect()
$array1 = array("a" => "green", "red", "blue");
$array2 = array("b" => "green", "yellow", "red");
$result = array_intersect($array1, $array2);
print_r($result);
>> green
red
Java - List.retain모두
Collection listOne = new ArrayList(Arrays.asList("milan","dingo", "elpha", "hafil", "meat", "iga", "neeta.peeta"));
Collection listTwo = new ArrayList(Arrays.asList("hafil", "iga", "binga", "mike", "dingo"));
listOne.retainAll( listTwo );
System.out.println( listOne );
>> dingo, hafil, iga
이것은 문자열 알고리즘처럼 보이기 때문에 잠시 이 시퀀스(따라서 문자열)를 정렬할 수 없다고 가정하면 Longest Common Sequence Algorithm(LCS; 최장 공통 시퀀스 알고리즘)을 사용할 수 있습니다.
입력 크기가 일정하다고 가정하면 문제의 복잡도는 O(nxm)(두 입력의 길이)입니다.
public static void main(String[] args) {
char[] a = {'a', 'b', 'c', 'd'};
char[] b = {'c', 'd', 'e', 'f'};
System.out.println(intersect(a, b));
}
private static Set<Character> intersect(char[] a, char[] b) {
Set<Character> aSet = new HashSet<Character>();
Set<Character> intersection = new HashSet<Character>();
for (char c : a) {
aSet.add(c);
}
for (char c : b) {
if (aSet.contains(c)) {
intersection.add(c);
}
}
return intersection;
}
int s[256] // for considering all ascii values, serves as a hash function
for(int i=0;i<256;i++)
s[i]=0;
char a[]={'a','b','c','d'};
char b[]={'c','d','e','f'};
for(int i=0;i<sizeof(a);i++)
{
s[a[i]]++;
}
for(int i=0;i<sizeof(b);i++)//checker function
{
if(s[b[i]]>0)
cout<<b[i];
}
complexity O(m+n);
m- length of array a
n- length of array b
구글 구아바
이에 대한 좋은 답변은 이미 많지만, 만약 당신이 라이브러리를 이용하여 게으른 코딩에 대해 원라이너 방식으로 접근하고 싶다면, 나는 구글 구아바(Java용)와 그 방법을 택할 것이다.
(수중에 컴파일러는 없습니다만, 기다려 주세요)
char[] A = {'a', 'b', 'c', 'd'};
char[] B = {'c', 'd', 'e', 'f'};
Set<Character> intersection = Sets.intersection(
Sets.newHashSet<Character>(Chars.asList(a)),
Sets.newHashSet<Character>(Chars.asList(b))
);
이는 두 어레이 모두 중복되지 않는다고 가정하고 있습니다.이 경우 데이터 구조 집합을 사용하는 것이 더 타당하고 이러한 종류의 작업을 보다 효율적으로 수행할 수 있습니다.특히 처음부터 일련의 기본 요소에서 시작하지 않는 경우에는 더욱 그렇습니다.
사용 사례에 맞는 경우도 있고 적합하지 않을 수도 있지만 일반적인 사례에 대한 간단한 접근 방식입니다.
- 양쪽 어레이를 정렬합니다.
- 그런 다음 공통 요소가 있거나 배열 중 하나가 끝에 도달할 때까지 루프를 수행합니다.
점근적으로, 이것은 정렬의 복잡성을 필요로 한다. 즉, O(NlogN) 여기서 N은 더 긴 입력 배열의 길이이다.
중복이 필요한 경우 해시 맵을 사용하여 목록A에 인덱스를 붙입니다.키에는 요소가 표시되고 값은 해당 요소가 표시된 횟수입니다.
A의 첫 번째 요소 및 모든 요소에 대해 반복하고 맵에 존재하지 않는 경우 값 1로 입력합니다.이미 맵에 존재하는 경우에는 그 값에 1을 추가합니다.
다음으로 B를 반복하고 값이 존재하면 1을 뺍니다.그렇지 않은 경우 해당 요소의 테이블 값에 -1을 입력합니다.
마지막으로 맵을 반복하여 값이 != 0인 요소에 대해서는 차분으로 출력합니다.
private static <T> List<T> intersectArrays(List<T> a, List<T> b) {
Map<T, Long> intersectionCountMap = new HashMap<T, Long>((((Math.max(a.size(), b.size()))*4)/3)+1);
List<T> returnList = new LinkedList<T>();
for(T element : a) {
Long count = intersectionCountMap.get(element);
if (count != null) {
intersectionCountMap.put(element, count+1);
} else {
intersectionCountMap.put(element, 1L);
}
}
for (T element : b) {
Long count = intersectionCountMap.get(element);
if (count != null) {
intersectionCountMap.put(element, count-1);
} else {
intersectionCountMap.put(element, -1L);
}
}
for(T key : intersectionCountMap.keySet()) {
Long count = intersectionCountMap.get(key);
if (count != null && count != 0) {
for(long i = 0; i < count; i++) {
returnList.add(key);
}
}
}
return returnList;
}
이것은 다음에서 실행됩니다.O(n)목록과 맵을 각각 한 번만 반복하기 때문입니다.여기서 Java에서 사용되는 데이터 구조는 효율적일 것입니다.HashMap는 목록의 가장 큰 크기를 처리할 수 있는 용량으로 구성됩니다.
사용하고 있습니다.LinkedList미지의 교차로에 대한 목록을 추가하고 반복할 수 있는 방법을 제공하기 때문에 반환을 위해 사용됩니다.
가장 좋은 방법은 어레이에서 전혀 시작하지 않는 것입니다.배열은 요소에 대한 랜덤 액세스에는 최적화되지만 검색에는 최적화되지 않습니다(교차를 찾는 것이 가장 중요합니다).교차로에 대해 말하는 것처럼 어레이를 세트로 간주해야 합니다.따라서 보다 적절한 데이터 구조를 사용합니다(Java에서는Set그러면 작업이 훨씬 더 효율적입니다.
트리를 사용할 수 있지만 시간은 O(n(log n)이며 요소는 비교할 수 있어야 합니다.
먼저 최적의 정렬 알고리즘을 사용하여 두 배열을 정렬합니다.
그런 다음 선형 검색을 통해 공통 요소를 얻을 수 있습니다.
추가 공간이 제공되면 해시 테이블을 사용하여 이를 수행할 수 있습니다.
루비로 말하면 된다
a = ['a', 'b', 'c', 'd']
b = ['c', 'd', 'e', 'f']
c = a & b
c는 ['c'',d']를 포함합니다.
먼저 두 개의 어레이를 정렬한 후 동일한 요소일 경우 어레이를 추가하여 반환하십시오.
코드는 다음과 같습니다.
public static void printArr(int[] arr){
for (int a:arr){
System.out.print(a + ", ");
}
System.out.println();
}
public static int[] intersectionOf(int[] arr1, int[] arr2){
Arrays.sort(arr1);
Arrays.sort(arr2);
printArr(arr1);
printArr(arr2);
int i=0, j=0, k=0;
int[] arr = new int[Math.min(arr1.length, arr2.length)];
while( i < arr1.length && j < arr2.length){
if(arr1[i] < arr2[j]){
i++;
} else if(arr1[i] > arr2[j]){
j++;
} else {
arr[k++] = arr1[i++];
j++;
}
}
return Arrays.copyOf(arr, k);
}
public static void main(String[] args) {
int[] arr1 = {1, 2, 6};
int[] arr2 = {10, 2, 5, 1};
printArr(intersectionOf(arr1,arr2));
}
출력:
arr1: 1, 2, 6,
arr2: 1, 2, 5, 10,
arr: 1, 2,
ANSI 문자를 다루고 있다고 가정합니다.Unicode의 경우 접근 방식이 비슷해야 합니다. 범위를 변경하기만 하면 됩니다.
char[] A = {'a', 'b', 'c', 'd'};
char[] B = {'c', 'd', 'e', 'f'};
int[] charset = new int[256]
for(int i=0; i<A.length; i++) {
charset[A[i]]++;
}
여기서 B를 통해 반복하면 반복되는 문자의 대응하는 문자 집합 값이 0보다 큰지 확인할 수 있습니다.목록 또는 다른 컬렉션에 저장할 수 있습니다.
이 방법에는 O(n) 시간의 복잡성과 체크에 일정한 공간이 필요합니다.이 경우 공통 요소를 유지하기 위해 사용되는 새로운 어레이/목록을 고려하지 않습니다.
이는 공간의 복잡성 측면에서 HashSet/Hashtable 접근 방식보다 우수합니다.
에서 HashSet을 사용할 수 있습니다.NET 3.5 이후c# 코드의 예:
HashSet<int> set1 = new HashSet<int>(new int[]{8, 12, 13, 15});
HashSet<int> set2 = new HashSet<int>(new int[] { 15, 16, 7, 8, 9 });
set1.IntersectWith(set2);
foreach (int i in set1)
Console.Write(i+ " ");
//출력: 8 15
어레이 중 하나를 정렬합니다(m Log(m)). 이제 다른 어레이에서 각 요소를 선택하여 첫 번째 어레이(정렬된 어레이)에서 바이너리 검색을 수행합니다.->n Log(m)
총 시간 복잡도:- (n+m) Log(m).
아래가 도움이 되었으면 합니다.이 두가지 다른 접근:.
단순 교차로 다른 배열에 한 배열에서 모든 요소를 비교한다.
이진 검색을 사용하여 1개의 어레이를 정렬하고 1개의 어레이에서 2번째 어레이 요소를 검색하는 정렬 및 검색 기반 접근법입니다.
//
public class IntersectionOfUnsortedArrays {
public static void main(String[] args) {
int[] arr1 = { 12, 4, 17 };
int[] arr2 = { 1, 12, 7, 17 };
System.out.println("Intersection Using Simple Comparision");
printArray(simpleIntersection(arr1, arr2));
System.out.println("Intersection Using Sort and Binary Search");
printArray(sortingBasedIntersection(arr1, arr2));
}
/*
* Simple intersection based on the comparison without any sorting.
* Complexity O(n^2)
*/
public static int[] simpleIntersection(int[] a, int[] b) {
int minlen = a.length > b.length ? b.length : a.length;
int c[] = new int[minlen];
int k=0;
for(int i=0;i<a.length;i++){
for(int j=0;j<b.length;j++){
if(a[i]==b[j]){
c[k++]=a[i];
}
}
}
int arr[] = new int[k];
// copy the final array to remove unwanted 0's from the array c
System.arraycopy(c, 0, arr, 0, k);
return arr;
}
/*
* Sorting and Searching based intersection.
* Complexity Sorting O(n^2) + Searching O(log n)
*/
public static int[] sortingBasedIntersection(int[] a, int[] b){
insertionSort(a);
int minlen = a.length > b.length ? b.length : a.length;
int c[] = new int[minlen];
int k=0;
for(int i=0;i<b.length;i++){
int result = binarySearch(a,0,a.length,b[i]);
if(result > -1){
c[k++] = a[result];
}
}
int arr[] = new int[k];
// copy the final array to remove unwanted 0's from the array c
System.arraycopy(c, 0, arr, 0, k);
return arr;
}
public static void insertionSort(int array[]) {
for (int i = 1; i < array.length; i++) {
int j = i;
int b = array[i];
while ((j > 0) && (array[j - 1] > b)) {
array[j] = array[j - 1];
j--;
}
array[j] = b;
}
}
static int binarySearch(int arr[], int low, int high, int num) {
if (high < low)
return -1;
int mid = (low + high) / 2;
if (num == arr[mid])
return mid;
if (num > arr[mid])
return binarySearch(arr, (mid + 1), high, num);
else
return binarySearch(arr, low, (mid - 1), num);
}
public static void printArray(int[] array) {
for (int value : array) {
System.out.print(" "+value);
}
System.out.println("\n");
}
}
질문에 나타난 것처럼 컬렉션이 이미 정렬되어 있는 경우 최적의 솔루션은 O(n+m)에서 실행되는 Marge-Sort와 같은 알고리즘입니다.
각 컬렉션의 첫 번째 요소를 비교합니다.동일한 경우 요소를 교차로 세트에 추가하고 두 요소를 모두 집합에서 팝합니다.요소가 다른 경우 다른 요소와 비교하여 더 큰 요소를 팝합니다.하나의 컬렉션이 비워질 때까지 반복합니다.
Java 8 기능을 사용하면 목록을 세트로 변환하는 대신 목록 내의 중복을 지원하는 알고리즘이 있습니다. 없기 「 」 「 」 「 」n log n.
- 리스트의 1개를 맵으로 변환합니다.값은 발생 횟수(비용: O(n))입니다.
- 다른 목록의 각 항목에 대해 해당 항목이 지도에 있는 경우 발생 횟수를 1회 줄입니다(비용: O(n).
따라서 전체 비용은 O(n)입니다.코드:
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Map;
import java.util.stream.Collectors;
public class Dup {
public static void main(String[] args) {
List<Integer> listA = Arrays.asList(3, 1, 4, 1, 9, 5, 9);
List<Integer> listB = Arrays.asList(2, 6, 5, 3, 5, 8, 9, 7, 9, 3, 2, 3);
findCommons(listA, listB);
}
static void findCommons(List<Integer> listA, List<Integer> listB) {
Map<Integer, Long> mapA =
listA.stream().collect(
Collectors.groupingBy(Integer::intValue, Collectors.counting()));
List<Integer> commons = new ArrayList<>();
listB.stream()
.filter(e -> mapA.get(e) != null)
.filter(e -> mapA.get(e) > 0)
.forEach(e -> {
mapA.put(e, mapA.get(e) - 1);
commons.add(e);
});
System.out.println(commons);
}
}
의 코드는 다음과 같은합니다.[5, 3, 9, 9].
import java.displaces.스캐너
공용 클래스 어레이 공통 {
public static void main(String[] args) {
Scanner sc=new Scanner(System.in);
// display common element in two diffrent array
int sizea,sizeb,i=0,j=0,k=0;
int count=0;
System.out.println("enter the size array A:"+'\n');
sizea=sc.nextInt();
System.out.println("enter the size array B"+'\n');
sizeb=sc.nextInt();
int a[]=new int[sizea];
int b[]=new int[sizeb];
int c[]=new int[sizea];
System.out.println("enter the element in array A:"+'\n');
for (i = 0; i < sizea; i++) {
a[i]=sc.nextInt();
}
System.out.println("enter the element in array B:"+'\n');
for (i = 0; i < sizeb; i++) {
b[i]=sc.nextInt();
}
System.out.println("the element in array A:"+'\n');
for (i = 0; i < sizea; i++) {
System.out.print(a[i]+" ");
}
System.out.println('\n');
System.out.println("the element in array B:"+'\n');
for (i = 0; i < sizeb; i++)
{
System.out.print(b[i]+" ");
}
for (i = 0; i <sizea; i++)
{
for (j = 0; j < sizeb; j++)
{
if(a[i]==b[j])
{
count++;
c[k]=a[i];
k=k+1;
}
}
}
System.out.println('\n');
System.out.println("element common in array is");
if(count==0)
{
System.out.println("sorry no common elements");
}
else
{
for (i = 0; i <count; i++)
{
System.out.print(c[i]+" ");
}
}
}
}
simply search each element of first array with each element of second array and stored matched result in third array
class Union
{
public static void main(String[] args) {
char a[] ={'f','g','d','v','a'};
char b[] ={'a','b','c','d','e'};
char temp[] = new char[5];
int p=0;
for(int i=0;i<a.length;i++)
{
for(int j=0;j<b.length;j++)
{
if(a[i]==b[j]) //searches if both array has common element
{
temp[p] = a[i]; //if match found store it in a new array
p++;
}
}
}
for(int k=0;k<temp.length;k++)
{
System.out.println(temp[k]);
}
}
}
언급URL : https://stackoverflow.com/questions/13270491/how-do-i-get-the-intersection-between-two-arrays-as-a-new-array
'source' 카테고리의 다른 글
| Java에서 일반 유형의 인스턴스를 생성하시겠습니까? (0) | 2022.07.21 |
|---|---|
| Vuex에서 작업이 완료되면 저장소에서 구성 요소 함수 호출 (0) | 2022.07.21 |
| 1988년식 C코드에 무슨 문제가 있나요? (0) | 2022.07.21 |
| VueJs의 워치 함수에 관한 2가지 메서드 호출 (0) | 2022.07.21 |
| Array List의 개체를 날짜별로 정렬하시겠습니까? (0) | 2022.07.21 |