Cách đếm có bao nhiêu số âm trong c++ mangt năm 2024

Question

Trong chương trình sau, chúng tôi đang kiểm tra xem số nguyên đầu vào là dương hay âm. Nếu số đầu vào lớn hơn 0 thì số dương của nó sẽ là số âm. Nếu con số bằng không thì nó không phải là số dương hay âm.

Để giải quyết bài toán trên bạn có thể dùng 1 mảng đánh dấu đủ lớn để đánh dấu sự xuất các giá trị trong mảng, vì các phần tử trong mảng đều nằm trong đoạn từ [0, 106] nên chỉ cần dùng một mảng số nguyên mà chỉ số của nó có thể đánh dấu được hết các giá trị [0, 106] là giải quyết được bài toán.

Ý tưởng ở đây đó là bạn sẽ sử dụng chỉ số của mảng đánh dấu để đánh dấu giá trị tương ứng với chỉ số đó đã xuất hiện trong mảng. Ban đầu tất cả các phần tử trong mảng đánh dấu có giá trị là 0, khi bạn gặp một giá trị trong mảng thì sẽ chuyển phần tử trong mảng đánh dấu tại chỉ số đó thành 1.

Ví dụ mảng đánh dấu là mark[] và khi gặp phần tử trong mảng A[] là 3 thì mark[3] = 1

Sau khi đánh dấu xong các giá trị xuất hiện thì bạn chỉ cần duyệt mảng đánh dấu và xem phần tử nào trong mảng đánh dấu có giá trị là 1 để đếm hoặc liệt kê.

Code :

include "iostream"

include "math.h"

using namespace std; int mark[1000001]; int main(){

int n = 8;  
int a[8] = {3, 1, 3, 0, 2, 4, 1, 6};  
for(int i = 0; i < n; i++){  
    mark[a[i]] = 1;  
}  
int dem = 0;  
for(int i = 0; i <= 1000000; i++){  
    if(mark[i] == 1){  
        ++dem;  
    }  
}  
cout << "So luong phan tu khac nhau : " << dem << endl;  
return 0;

}

Output :

So luong phan tu khac nhau : 6

Giải thích :

Mảng mark ban đầu :

i01234567.......mark[i]000000000.....

i = 0, a[i] = 3, mark[3] = 1

i01234567.......mark[i]000100000.....

i = 1, a[i] = 1, mark[1] = 1

i01234567.......mark[i]010100000.....

i = 2, a[i] = 3, mark[3] = 1

i01234567.......mark[i]010100000.....

....

i = 7, a[i] = 6, mark[6] = 1

i01234567.......mark[i]111110100.....

Chú ý khi sử dụng mảng đánh dấu :

Mảng đánh dấu không thể sử dụng được với số âm, vì chỉ số trong mảng không thể là số âm
Mảng đánh dấu không sử dụng được khi giá trị cần đánh dấu vượt chỉ số của mảng mà bạn có thể khai báo
Thông thường bạn chỉ áp dụng được kỹ thuật này khi các phần tử trong mảng có giá trị trong đoạn [0, 107]
Chú ý sử dụng mảng đánh dấu đủ lớn để không lỗi bộ nhớ, ví dụ bạn cần đánh dấu các phần tử trong đoạn [0, 103] thì mảng cỡ 1001 là đủ rồi, hoặc có thể lớn hơn

2.Bài Toán Liệt Kê Giá Trị Khác Nhau

Bài Toán 1 : Cho mảng A[] gồm N phần tử là số nguyên trong đoạn [0, 106], hãy liệt kê các giá trị khác nhau trong mảng theo thứ tự từ nhỏ tới lớn

Ý tưởng là sử dụng mảng đánh dấu sau đó liệt kê các số từ nhỏ tới lớn xuất hiện trong mảng và in ra nếu giá trị đó được đánh dấu.

Code :

include "iostream"

include "math.h"

using namespace std; int mark[1000001]; int main(){

int n = 10;  
int a[10] = {3, 1, 3, 0, 2, 4, 1, 14, 12, 7};  
int max_val = -1000000000;  
for(int i = 0; i < n; i++){  
    mark[a[i]] = 1;  
    if(a[i] > max_val){  
        max_val = a[i];  
    }  
}  
cout << "Cac gia tri khac nhau trong mang : ";  
for(int i = 0; i <= max_val; i++){  
    if(mark[i] == 1){  
        cout << i << " ";  
    }  
}  
return 0;

}

Output :

Cac gia tri khac nhau trong mang : 0 1 2 3 4 7 12 14

Bài Toán 2 : Cho mảng A[] gồm N phần tử là số nguyên trong đoạn [0, 106], hãy liệt kê các giá trị khác nhau trong mảng theo thứ tự xuất hiện trong mảng, mỗi giá trị chỉ liệt kê 1 lần

Ý tưởng là sử dụng mảng đánh dấu sau đó liệt kê các theo thứ tự xuất hiện trong mảng và in ra nếu giá trị đó được đánh dấu.

Sau khi in ra giá trị thì bạn bỏ đánh dấu giá trị đó để tránh in trùng.

Code :

include "iostream"

include "math.h"

using namespace std; int mark[1000001]; int main(){

int n = 10;  
int a[10] = {3, 1, 3, 0, 2, 4, 1, 14, 12, 7};  
for(int i = 0; i < n; i++){  
    mark[a[i]] = 1;  
}  
cout << "Gia tri khac nhau trong mang : ";  
for(int i = 0; i < n; i++){  
    if(mark[a[i]] == 1){  
        cout << a[i] << " ";  
        mark[a[i]] = 0;  
    }  
}  
return 0;

}

Output :

Gia tri khac nhau trong mang : 3 1 0 2 4 14 12 7

3. Bài Toán Tần Suất

Mảng đánh dấu rất hữu dụng đối với những bài toán liên quan tới tần suất xuất hiện của phần tử trong mảng.

Trong bài toán liên quan tới tần suất thì mảng đánh dấu mark[] có vai trò đếm tần suất thay vì chỉ đánh dấu. Khi đánh dấu giá trị a[i] trong mảng thì bạn cần cho mark[a[i]] = 1 còn khi bạn muốn đếm xem a[i] đã xuất hiện bao nhiêu lần thì bạn thay đổi câu lệnh cập nhật thành mark[a[i]]++

Bài toán : Cho mảng A[] gồm N phần tử là số nguyên trong đoạn [0, 106], hãy đếm xem mỗi phần tử trong mảng xuất hiện bao nhiêu lần và in ra theo thứ tự từ nhỏ tới lớn.

Code :

include "iostream"

include "math.h"

using namespace std; int mark[1000001]; int main(){

int n = 10;  
int a[10] = {3, 1, 3, 0, 2, 4, 1, 14, 3, 2};  
int max_val = -1000000000;  
for(int i = 0; i < n; i++){  
    mark[a[i]]++;  
    if(a[i] > max_val){  
        max_val = a[i];  
    }  
}  
for(int i = 0; i <= max_val; i++){  
    if(mark[i]){  
        cout << i << " xuat hien " << mark[i] << " lan\n";  
    }  
}  
return 0;

}

Output :

0 xuat hien 1 lan 1 xuat hien 2 lan 2 xuat hien 2 lan 3 xuat hien 3 lan 4 xuat hien 1 lan 14 xuat hien 1 lan

Các bài toán sau bạn tự triển khai coi như bài tập :

Bài 1. Liệt kê các phần tử xuất hiện ít nhất 2 lần trong mảng theo thứ tự xuất hiện trong mảng, mỗi phần tử chỉ liệt kê 1 lần

Ví dụ A[] = {3, 1, 1, 1, 2, 3, 4, 0, 3, 2} thì output sẽ là 3, 1, 2

Bài 2. Liệt kê các phần tử xuất hiện đúng 1 lần trong mảng theo thứ tự xuất hiện trong mảng

Ví dụ A[] = {3, 1, 1, 1, 2, 3, 4, 0, 3, 2} thì output sẽ là 4, 0, 2

Bài 3. Liệt kê các phần tử xuất hiện nhiều nhất trong mảng, nếu có nhiều phần tử có cùng số lần xuất hiện nhiều nhất thì liệt kê theo thứ tự xuất hiện trong mảng

Ví dụ A[] = {3, 1, 1, 1, 2, 3, 4, 0, 3, 2} thì output sẽ là 3, 1

Bài 4. Cho mảng A[] và B[], hãy liệt kê các giá trị thuộc 1 trong 2 mảng, mỗi giá trị liệt kê 1 lần theo thứ tự tăng dần

bao nhieu Hỏi Đáp Bao nhiêu Mẹo Hay Cách