Tìm Giao Hai Tập Hợp (Sửa bài)

[pvt3919vn]

[TẶNG BẠN] TRỌN BỘ Bí kíp học tốt 08 môn
Chắc suất Đại học top - Giữ chỗ ngay!!

ĐĂNG BÀI NGAY để cùng trao đổi với các thành viên siêu nhiệt tình & dễ thương trên diễn đàn.

[FONT="Courier New"]uses crt;
type mang=array[1..100] of integer;
var A,B : mang;
    i,j,m,n : integer;
    ff : boolean;

procedure nhapmang(var c:mang;var k:integer);
var i,j,x : integer;
    cc  : char;
    f : boolean;
begin
k:=0;
repeat f:=true;
       Write('nhap phan tu >>> '); readln(x);
       for i:=1 to k do
         begin
           if x=c[i] then
                begin
                  f:=false;
                  break;
                end;
           if f=true then
                begin
                  k:=k+1;
                  c[i]:=x;
                end;
         end;
         Writeln;
         Writeln('nhan ESC de ket thuc nhap/ phim bat ki de tiep tuc');
           cc:=readkey;
Until cc=#27;
end;

begin
clrscr;
        nhapmang(A,n); nhapmang(B,m);



        ff:=false;
        i:=1;
        j:=1;
        While (i<=n) and (not ff) do
         if B[j]=A[i] then
         begin
          Write(A[i]);
          j:=j+1;
         end else
         begin
          i:=i+1;
         end;
		 
		 
		 

end.[/FONT]

Em viết đến đây bó tay.com

 

[lamdetien36]

Nếu giới hạn N nhỏ thì cứ duyệt trâu, với mỗi A, tìm B[j] = A, nếu có B[j] thì in ra A.
Nếu N lớn thì:
- Nếu có thêm giới hạn của A và B[j] thì quá đơn giản, chỉ cần đếm phân phối là xong.
- Nếu không có giới hạn của A, B[j] thì sort 2 mảng lại, rồi 2-pointers là xong. Cụ thể:

int main() {
    int A[10000], B[10000], M, N, i, j;

    cin >> M >> N;
    for (i = 0; i < M; ++i)
        cin >> A[i];
    for (j = 0; j < N; ++j)
        cin >> B[j];
    sort(A, A + M);
    sort(B, B + N);

    for (i = j = 0; i < M && j < N;) {
        if (B[j] == A[i]) {
            cout << A[i] << " ";
            i++; j++;
        }
        else {
            if (B[j] > A[i])
                i++;
            else
                j++;
        }
    }

    return 0;
}

Bạn tự dịch sang Pascal nhé, code cũng đơn giản mà

 

[lamdetien36]

Code Pascal:

type
    Arr = array [1..10000] of integer;
var
    A, B: Arr;
    M, N, i, j: integer;
procedure Swap(var x, y: integer);
 var
     z: integer;
 begin
     z := x;
     x := y;
     y := z;
 end;
procedure sort(var A: Arr; L, R: integer);
 var
     piv, i, j: integer;
 begin
     if (L >= R) then exit;
     piv := A[(L + R) div 2];
     i := L; j := R;
     repeat
         while (A[i] < piv) do
             i := i + 1;
         while (A[j] > piv) do
             j := j - 1;
         if (i <= j) then
         begin
             Swap(A[i], A[j]);
             i := i + 1;
             j := j - 1;
         end;
     until i > j;
     sort(A, L, j);
     sort(A, i, R);
 end;
begin
    readln(M, N);
    for i := 1 to M do
        readln(A[i]);
    for j := 1 to N do
        readln(B[j]);
    sort(A, 1, M);
    sort(B, 1, N);
    
    i := 1; j := 1;
    while (i <= M) and (j <= N) do
    begin
        if (B[j] = A[i]) then
        begin
            write(A[i], ' ');
            i := i + 1;
            j := j + 1;
        end
        else
        begin
            if (B[j] > A[i]) then
                i := i + 1
            else
                j := j + 1;
        end;
    end;
end.

Dài gấp 3 lần.