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

HOME › >>

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

Có thể xóa phần tử trùng nhau 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à dịch chuyển nội bộ các phần tử không trùng nhau về một phía của mảng và chỉ sử dụng các phần tử này trong mảng 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ó 2 phương pháp khác nhau để xoá phần tử trùng nhau trong mảng C++ theo logic ở trên như dưới đây.

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

Ý 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 các phần tử không trùng nhau đã được chuyển lên đầu mảng
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

Ở phần trên chúng ta đã di chuyển các phần tử không trùng nhau lên đầu mảng ban đầu. Nếu bạn muốn lấy riêng các phần tử trùng nhau ra, hãy viết thêm xử lý lấy các phần tử này và gán vào một mảng mới nhé.

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

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 đè array[j] bằng phạm vi từ array[j + 1] đến cuối mảng, qua đó xoá array[j]
memmove(&array[j], &array[j + 1], sizeof(int) * (size - j - 1));

--size; // Do đã xoá array[j] nên trừ độ dài mảng đi một đơn vị

// 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 lại vị trí j bằng cách giảm giá trị của j 1 đơn vị
--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.

URL Link

https://laptrinhcanban.com/cpp/lap-trinh-cpp-co-ban/mang-trong-cpp/xoa-phan-tu-trung-trong-mang-cpp/

Hãy chia sẻ và cùng lan tỏa kiến thức lập trình Nhật Bản tại Việt Nam!

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.