Loại bỏ phần tử trùng của hai mảng

#1

Một bài giải thuật vui nữa :slight_smile:

Cho hai mảng có m và n phần tử. Hai mảng này chứa số CMND, có trùng. Tạo ra một mảng mới với toàn bộ các số CMND, không trùng.

Phân tích time complexity và space compexity khi

  • m ~ n : số lượng phần tử gần bằng nhau
  • m >> n : m nhiều hơn hẳn n

Input:

  • m: số phần tử mảng 1
  • các phần tử mảng 1
  • n: số phần tử mảng 2
  • các phần tử mảng 2

Output:

mảng mới, không trùng

Ví dụ:

Input mẫu:

8
1 2 5 4 7 8 9 6
5
4 11 12 7 6

Output mẫu:

1 2 5 4 7 8 9 6 11 12

Luật bất thành văn:

  • Có thể sử dụng mọi ngôn ngữ
  • Phân tích cách giải quyết vấn đề
3 Likes
#2

C với C++ trước:

Dùng qsort: time: (m+n)log(m+n), space: m+n

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int compare_int(const void *a,const void *b){
    return *(int *)a - *(int *)b;
}

int main(){
    int n,m;
    scanf("%d",&n);
    int *a=malloc(sizeof(int)*n);
    int i;
    for(i=0;i<n;++i){
        scanf("%d",a+i);
    }
    scanf("%d",&m);
    int *b=malloc(sizeof(int)*(m+n));
    for(i=0;i<m;++i){
        scanf("%d",b+i);
    }
    memcpy(b+m,a,n*sizeof(int));
    int len=0;
    int lastNumber;
    qsort(b,m+n,sizeof(int),compare_int);

    for(i=0;i<m+n;i++){
        if(len==0 || lastNumber!=b[i]){
            lastNumber=b[i];
            printf("%d ",lastNumber);
            len++;
        }
    }
    free(a);
    free(b);
    return 0;
}

C++

#include <iostream>
#include <set>

using namespace std;


int main(){
    int n;
    int x;
    set<int> S;
    for(int i=0;i<2;i++){
        cin>>n;
        while(n--){
            cin>>x;
            S.insert(x);
        }
    }
    for(auto x: S){
        cout<<x<<" ";
    }
    return 0;
}

Tương tự code cpp cho python:

n=input()
a=set(map(int,raw_input().split()))
m=input()
b=set(map(int,raw_input().split()))
print a|b
3 Likes
#3

Em dùng Python, đưa vào set mọi phần tử mảng 1 và mảng 2.

def solve(list1, m, list2, n):
    result =set(list1)

    for element in list2:
        result.add(element)

    return list(result)

space (m+n)
time O(m+n)
mỗi mảng có phần tử trùng trong đó không anh?

3 Likes
#4

Với giải thuật của em thì đâu quan trọng?

1 Like
#5

Nếu nhờ “hỗ trợ” từ ngôn ngữ thì sử dụng STL unordered_set C++ hoặc HashSet java hoặc các cấu trúc tương đương trong các ngôn ngữ khác nếu có để làm. Time complexity: O(N+M), extra space complexity: O(N+M)
Nếu tự thân vận động thì sort lại 2 mảng ban đầu, sau đó sử dụng two pointer, dùng 2 biến chỉ số chạy song song trên 2 mảng để insert vào mạng thứ 3. Time complexity: O(NlogN + MlogM), extra space complexity: O(N+M)

2 Likes
#6

Ngoài ra ở cách thứ 2, nếu ai không quen dùng Two pointer (đoạn sử dụng two pointer để tạo mảng C không trùng này là O(N+M)), thì vẫn có thể làm theo một cách khác:

  • gom tất cả N+M phần tử vào mảng C
  • sort lại mảng C gồm N+M phần tử đó
  • gọi k là số phần tử thực có trong mảng C. Tức số phần tử không trùng.
  • mặc định k = min(1, n+m) (trường hợp ai chơi ác nhập 2 mảng rỗng.
  • duyệt i từ 1 đến N+M-1, nếu C[i] != C[k-1], nếu phần tử đang xét không trùng với phần tử cuối cùng được chọn thực sự của mảng kết quả C thì tức đây là lần xuất hiện đầu tiên C[i] trong tập -> thêm nó vào mảng C thực: C[k++] = C[i].
    Space complexity vẫn là O(N+M) nhưng time complexity là O((N+M)log(N+M))
    Nếu phân tích kỹ thì cả 2 cách sort rời 2 mảng và gộp 2 mảng lại sort, ở đoạn duyệt sau khi sort xong đều có thêm 1 chi phí tuyến tính O(N+M), nhưng khi N, M lớn thì nó không là gì so với NlogN, MlogM hay (N+M)log(N+M) nên có thể bỏ qua nó luôn
1 Like
#7

Bài em thì chủ yếu ở set
Hỏi vẩn vơ thôi, tại thấy có trường hợp m>>n, với trường hợp này thì space là O(m), time O(m).
:grimacing: lâu không làm, để nhớ lại bài nào đăng chơi câu view xem.

1 Like
#8

có cái std::set_union cũng hay lắm đó

#include <iostream>
#include <vector>
#include <algorithm>

int main()
{
    int n;
    
    std::cin >> n;
    std::vector<int> a(n);
    for (int& x : a) std::cin >> x;
    
    std::cin >> n;
    std::vector<int> b(n);
    for (int& x : b) std::cin >> x;
    
    std::sort(begin(a), end(a));
    std::sort(begin(b), end(b));
    
    std::vector<int> anb;
    std::set_intersection(begin(a), end(a), begin(b), end(b), std::back_inserter(anb));
    std::cout << "A intersects B = ";
    for (int x : anb) std::cout << x << " ";
    std::cout << "\n";
    
    std::vector<int> aub;
    std::set_union(begin(a), end(a), begin(b), end(b), std::back_inserter(aub));
    std::cout << "A unions B = ";
    for (int x : aub) std::cout << x << " ";
    std::cout << "\n";
    
    std::vector<int> amb;
    std::set_difference(begin(a), end(a), begin(b), end(b), std::back_inserter(amb));
    std::cout << "A \\ B = ";
    for (int x : amb) std::cout << x << " ";
    std::cout << "\n";
}

với input như trên thì nó in ra:

A intersects B = 4 6 7 
A unions B = 1 2 4 5 6 7 8 9 11 12 
A \ B = 1 2 5 8 9

khỏe re :stuck_out_tongue:

2 Likes
#9

có thể ko cần mảng thứ 3 vẫn được chứ nhỉ? Khi “merge” 2 mảng đã sorted lại chỉ cần nhớ phần tử cuối cùng của mảng thứ 3 là được. Merge tới đâu xuất tới đó khỏi cần mảng thứ 3.

1 Like
#10

nếu chỉ xuất không thì chỉ cần 2 mảng ban đầu là được :smiley:

83% thành viên diễn đàn không hỏi bài tập, còn bạn thì sao?