두 어레이 사이의 교차점을 새 어레이로 어떻게 얻습니까?
다양한 상황에서이 문제에 여러 번 직면했습니다. C 또는 Java에 익숙하지만 모든 프로그래밍 언어에 일반적입니다.
두 개의 배열 (또는 컬렉션)을 고려해 보겠습니다.
char[] A = {'a', 'b', 'c', 'd'};
char[] B = {'c', 'd', 'e', 'f'};
두 배열 사이의 공통 요소를 새 배열로 어떻게 얻습니까? 이 경우 배열 A와 B의 교차점은입니다 char[] c = {'c', 'd'}.
나는 거대한 배열의 경우 너무 많은 실행 시간을 (A의 길이와 B의 길이) 증가시키는 다른 배열 내부의 한 배열의 반복 반복을 피하고 싶습니다.
공통 요소를 얻기 위해 각 배열에서 단일 패스를 수행 할 수있는 방법이 있습니까?
이것은 나에게 문자열 알고리즘처럼 보이기 때문에 잠시이 시퀀스 (따라서 문자열)를 정렬 할 수 없다고 가정하고 LCS (Longest Common Sequence Algorithm )를 사용할 수 있습니다.
입력 크기가 일정하다고 가정하면 문제의 복잡성은 O (nxm) (두 입력 길이)입니다.
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).
해시 접근
배열 하나의 요소에서 해시 테이블을 만듭니다. 해시 테이블의 두 번째 테이블에서 요소를 검색합니다. 시간 복잡도는 해시 함수에 따라 다릅니다. 최적의 경우 (모든 요소가 다른 해시 값을 가짐)에서 검색에 대해 O (1)을 달성 할 수 있지만, 최악의 경우 (모든 요소가 동일한 해시 값을 가짐) O (n)을 얻을 수 있습니다. 총 시간 복잡도 : O (n ^ x), 여기서 x는 해시 함수 효율성의 요소입니다 (1과 2 사이).
일부 해시 함수는 충돌없이 테이블을 빌드하도록 보장됩니다. 그러나 건물은 더 이상 모든 요소에 대해 엄격하게 O (1) 시간이 걸리지 않습니다. 대부분의 경우 O (1)이지만 테이블이 가득 차거나 충돌이 발생하면 테이블을 다시 해시해야합니다. O (n) 시간이 걸립니다. 이것은 자주 발생하지 않으며 깨끗한 추가보다 훨씬 덜 자주 발생합니다. 따라서 AMORTIZED 시간 복잡도는 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
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
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
Google 구아바
이에 대한 좋은 답변은 이미 많이 있지만 지연 코딩을 위해 라이브러리를 사용하는 한 줄짜리 접근 방식을 원한다면 Google Guava (Java 용) 및 그 Sets.intersection방법을 사용 하겠습니다 .
(컴파일러가 없으니 참아주세요)
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로 넣고 맵에 이미있는 경우 해당 값에 추가합니다.
그런 다음 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)Lists를 한 번만 반복하고 Map을 한 번만 반복하므로 에서 실행되어야합니다 . 여기서 Java에서 사용되는 데이터 구조 HashMap는 목록의 가장 큰 크기를 처리 할 수있는 용량으로 구성 되므로 효율적이어야 합니다.
LinkedList알 수없는 크기의 교차로에 대한 목록을 추가하고 반복하는 방법을 제공하므로 반환을 위해를 사용하고 있습니다.
가장 좋은 방법은 배열로 시작하지 않는 것입니다. 배열은 요소에 대한 임의 액세스에 최적이지만 검색에는 최적이 아닙니다 (교차를 찾는 것이 전부입니다). 교차점 에 대해 이야기 할 때 배열을 세트로 간주해야합니다. 따라서 더 적절한 데이터 구조를 사용하십시오 (Java에서는 a 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 문자를 다루고 있다고 가정합니다. 접근 방식은 유니 코드와 비슷해야하며 범위 만 변경하면됩니다.
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 접근 방식보다 낫습니다.
.NET 3.5 이상에서 HashSet을 사용할 수 있습니다. 예제 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) .
다음이 도움이 되길 바랍니다. 두 가지 접근 방식이 있습니다.
한 배열의 모든 요소를 다른 배열과 비교하는 단순 교차점.
이진 검색을 사용하여 첫 번째 배열에서 두 번째 배열 요소를 검색하고 하나의 배열을 정렬하는 정렬 및 검색 기반 접근 방식입니다.
//
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)에서 실행되는 병합 정렬 유사 알고리즘입니다.
각 컬렉션의 첫 번째 요소를 비교합니다. 동일하다면 교차 세트에 요소를 추가하고 컬렉션에서 두 요소를 모두 팝합니다. 요소가 다른 경우 다른 요소에 비해 더 큰 요소를 팝합니다. 한 컬렉션이 비워 질 때까지 반복합니다.
Java 8 기능을 사용하여 목록을 집합으로 바꾸는 대신 목록 내의 중복을 인식하는 알고리즘이 있습니다. 정렬이 없으므로 n log n.
- 목록 중 하나를 맵으로 변환하고 값은 발생 횟수입니다 (비용 : 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.util.Scanner;
공용 클래스 arraycommon {
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]);
}
}
}
'Nice programing' 카테고리의 다른 글
| Vim에서 강조 표시된 클래스 및 함수 이름 (0) | 2020.11.06 |
|---|---|
| indexPath로 uitableViewCell을 어떻게 얻을 수 있습니까? (0) | 2020.11.06 |
| Python에서 3D 산점도를 만드는 방법은 무엇입니까? (0) | 2020.11.04 |
| 모든 사용자에게 내 응용 프로그램에서 만든 파일에 대한 전체 권한을 부여하는 방법은 무엇입니까? (0) | 2020.11.04 |
| Django ModelForm : save (commit = False)는 무엇에 사용됩니까? (0) | 2020.11.04 |