Xóa phần tử trùng trong mảng C++ | Laptrinhcanban.com

Xóa phần tử trùng trong mảng C++

Hướng dẫn cách xoá phần tử trùng trong mảng C++. Bạn sẽ học được 2 cách căn bản để xoá phần tử trùng trong mảng C++ sau bài học này.

Chúng ta có 2 cách xóa phần tử trùng trong mảng C++ như sau:

  • Xóa phần tử trùng trong mảng C++ khi mảng đã được sắp xếp
  • Xóa phần tử trùng trong mảng C++ khi mảng chưa được sắp xếp

Logic xoá phần tử trùng trong mảng C++

Giả sử chúng ta có mảng chứa các phần tử trùng nhau như sau:

int array= {1, 2, 3, 1, 3, 2, 4};

Ở mảng này, các phần tử là 1, 2 và 3 là phần tử trùng nhau, và sau khi xoá phần tử trùng nhau, mảng kết quả sẽ là {1,2,3,4}.

Tuy nhiên khác với các ngôn ngữ lập trình khác thì mảng trong C++ có kích thước cố định được quyết định khi khai báo mảng, và chúng ta không thể thay đổi kích thước của mảng sau khi khai báo.

Bởi vậy, chúng ta không thể xóa phần tử trong mảng C++, sau khi đã tạo nó. Điều duy nhất chúng ta có thể làm, đó là tạm coi như là số lượng phần tử đã giảm đi mặc dù trên thực tế, số lượng phần tử của mảng không thay đổi mà thôi.

Lại nữa, tốc độ xoá phần tử trùng trong mảng C++ khi mảng đó đã được hoặc chưa được sắp xếp là khác nhau. Và do vậy, chúng ta sẽ có 3 phương pháp khác nhau để xoá phần tử trùng nhau trong mảng C++ như Kiyoshi sẽ phân tích dưới đây.

Xóa phần tử trùng trong mảng C++ khi mảng đã được sắp xếp

Đây là cách 1 trong trường hợp mảng cần xoá phần tử trùng đã được sắp xếp từ trước. Ý tưởng ở đây là, sau khi sắp xếp mảng, thì các phần tử trùng nhau (nếu có) sẽ được xếp nằm cạnh nhau, do đó chúng ta chỉ cần kiểm tra 2 phần tử trùng nhau xem chúng có bằng nhau hay không là có thể xác định được các phần tử trùng nhau trong mảng.

Và khi tìm thấy các phần tử trùng nhau rồi, chúng ta sẽ lần lượt chuyển chúng về phía đầu mảng bằng cách ghi đè giá trị lên các phần tử ở đầu mảng. Và sau đó chỉ cần lấy toàn bộ các phần tử này từ trong mảng là chúng ta có thể hoàn thành việc xóa phần tử trùng trong mảng C++ rồi.

Để sắp xếp mảng, chúng ta sẽ sử dụng tới hàm qsort() mà Kiyoshi đã hướng dẫn trong bài:

Và chúng ta viết hàm xóa phần tử trùng trong mảng C++ trong chương trình như sau:

#include <iostream>
#include <cstdlib>
using namespace std;

/*Tạo macro SIZE_OF_ARRAY để lấy độ dài (số phần tử) của mảng chỉ định*/
#define SIZE_OF_ARRAY(array) (sizeof(array)/sizeof(array[0]))

/*Tạo hàm in phần tử trong mảng*/
void show_array(int array[], int length){
for(short i = 0; i < length; i++) cout << array[i] <<' ';
cout << endl;
}
/*Tạo hàm so sánh tăng dần sử dụng trong hàm qsort*/
int compareIntAsc(const void* a, const void* b)
{
int aNum = *(int*)a;
int bNum = *(int*)b;

return aNum - bNum;
}

/*Tạo hàm xoá phần tử trùng trong mảng C++*/
size_t array_unique(int* array, size_t size)
{
size_t end = 0;

for (size_t i = 1; i < size; ++i) {
if (array[i] != array[end]) { //Tìm thấy phần tử trùng nhau
++end; //Tăng dần vị trí đầu mảng để gán phần tử trùng nhau
array[end] = array[i]; //Ghi đè phần tử trùng nhau vào vị trí đầu mảng
}
}

return end + 1;
}

int main()
{
int array1[] = { 7, 2, 6, 7, 4, 9, 8 };
int array2[] = { 7, 2, 6, 7, 7 };
int array3[] = { 7, 7, 7 };

// Sắp xếp các mảng theo thứ tự tăng dần
qsort(array1, SIZE_OF_ARRAY(array1), sizeof(int), compareIntAsc);
qsort(array2, SIZE_OF_ARRAY(array2), sizeof(int), compareIntAsc);
qsort(array3, SIZE_OF_ARRAY(array3), sizeof(int), compareIntAsc);

//Xoá phần tử trùng nhau trong các mảng
size_t size1 = array_unique(array1, SIZE_OF_ARRAY(array1));
size_t size2 = array_unique(array2, SIZE_OF_ARRAY(array2));
size_t size3 = array_unique(array3, SIZE_OF_ARRAY(array3));

//in mảng sau khi đã xoá phần tử trùng nhau
show_array(array1, size1);
show_array(array2, size2);
show_array(array3, size3);

return 0;
}

Kết quả chương trình xóa phần tử trùng trong mảng C++:

2 4 6 7 8 9 
2 6 7
7

Xóa phần tử trùng trong mảng C++ khi mảng chưa được sắp xếp

Đây là cách 1 trong trường hợp mảng cần xoá phần tử trùng chưa được sắp xếp từ trước.

Trong mảng C++, cũng có những mảng mà chúng ta không thể sắp xếp mảng, hoặc là không có quyền sắp xếp mảng đó. Khi đó, chúng ta sẽ cần tới cách không sắp xếp mảng mà vẫn có thể xoá được phần tử trùng nhau trong mảng đó.

Để kiểm tra phần tử trùng trong mảng C++, chúng ta có thể lấy lần lượt từng phần tử và so sánh xem có phần tử nào giống nó trong chuỗi ban đầu hay không.

Nếu tồn tại dù chỉ một cặp phần tử giống nhau, điều đó có nghĩa là tồn tại phần tử trùng nhau trong mảng ban đầu, và ngược lại nếu tất cả đều khác nhau thì không tồn tại phần tử trùng nhau trong mảng ban đầu.

Để làm được điều đó, chúng ta cần dùng tới một vòng lặp lồng để lấy và kiểm tra từng phần tử trong mảng ban đầu.

Và cách xóa phần tử trùng trong mảng C++ khi mảng chưa được sắp xếp như sau:

#include <iostream>
#include <cstring>
using namespace std;

/*Tạo macro SIZE_OF_ARRAY để lấy độ dài (số phần tử) của mảng chỉ định*/
#define SIZE_OF_ARRAY(array) (sizeof(array)/sizeof(array[0]))

/*Tạo hàm in phần tử trong mảng*/
void show_array(int array[], int length){
for(short i = 0; i < length; i++) cout << array[i] <<' ';
cout << endl;
}
/*Tạo hàm xoá phần tử trùng trong mảng C++*/
size_t array_unique(int* array, size_t size)
{
for (size_t i = 0; i < size - 1; ++i) {
for (size_t j = i + 1; j < size; ++j) {
if (array[i] == array[j]) { //Tìm thấy phần tử trùng nhau


// Để ghi đè phần tử array[j]
// Chúng ta copy phạm vi từ array[j + 1] đến array[size - 1]
memmove(&array[j], &array[j + 1], sizeof(int) * (size - j - 1));

// Giảm số phần tử
--size;

// Do có khả năng 3 phần tử trùng nhau xuất hiện liên tiếp
// Nên chúng ta cần kiểm tra vị trí j và giảm giá trị của j
--j;
}
}
}

return size;
}


int main()
{
int array1[] = { 7, 2, 6, 7, 4, 9, 8 };
int array2[] = { 7, 2, 6, 7, 7 };
int array3[] = { 7, 7, 7 };

//Xoá phần tử trùng nhau trong các mảng
size_t size1 = array_unique(array1, SIZE_OF_ARRAY(array1));
size_t size2 = array_unique(array2, SIZE_OF_ARRAY(array2));
size_t size3 = array_unique(array3, SIZE_OF_ARRAY(array3));

//in mảng sau khi đã xoá phần tử trùng nhau
show_array(array1, size1);
show_array(array2, size2);
show_array(array3, size3);

return 0;
}

Kết quả chương trình xóa phần tử trùng trong mảng C++:

2 4 6 7 8 9 
2 6 7
7

Tổng kết

Trên đây Kiyoshi đã hướng dẫn bạn cách xoá phần tử trùng trong mảng C++ rồi. Để nắm rõ nội dung bài học hơn, bạn hãy thực hành viết lại các ví dụ của ngày hôm nay nhé.

Và hãy cùng tìm hiểu những kiến thức sâu hơn về C++ trong các bài học tiếp theo.

HOME>> >>

Profile
きよしです!笑

Tác giả : Kiyoshi (Chis Thanh)

Kiyoshi là một cựu du học sinh tại Nhật Bản. Sau khi tốt nghiệp đại học Toyama năm 2017, Kiyoshi hiện đang làm BrSE tại Tokyo, Nhật Bản.