[Thuật toán] Cần tìm cách giải khác cho một nài toán cũ rích

[11520537]

Chào mọi người,

Hôm nay một nhóc học CNTT (không phải trường mình) có hỏi mình một bài toán về duyệt mảng một chiều nhưng cách giải của em thì không vừa lòng nó. Bài toán như sau:
"Cho một mảng số nguyên, in ra các phần tử (a) chỉ xuất hiện duy nhất một lần, (b) xuất hiện nhiều hơn 1 lần và không được in trùng."
Vd: arr[15] = {1, 2, 3, 4, 1, 6, 2, 3, 7, 1, 7, 1, 8, 4, 1};
thì dòng 1 in ra là: 6, 8
dòng 2 in ra là: 1, 2, 3, 4, 7

Về cách giải quyết câu a thì không cần phải bàn. Vấn đề nằm ở câu b, vì không chuyên tâm vào cái này nên cách của mình là sử dụng thêm một mảng, và bắt đầu với việc duyệt mảng ban đầu, gặp phần tử nào chưa trùng thì lưu nó vào mảng, cuối cùng là in ra mảng này. Nhưng thằng nhóc không chịu vì nó nói không muốn dùng mảng để lưu, nó muốn duyệt mảng ban đầu trực tiếp rồi in ra luôn.

Vì thế bạn nào có cách giải thỏa được lòng thằng nhóc thì đưa ra cùng thảo luận.

[11520031]

Có thể dùng cách này thử xem
Trước tiên loại 2 phần tử xuất hiện 1 lần duy nhất bằng cách cho nó về 0 luôn. Sau đó
for (i=0,i++,i<15)
for (j=0,j++,j<15)
if (a[i]==a[j]) a[j]=0;
for (i=0,i++,i<15)
if (a[i]!=0) printf(a[i],' ');

[11520537]

Có thể dùng cách này thử xem
Trước tiên loại 2 phần tử xuất hiện 1 lần duy nhất bằng cách cho nó về 0 luôn. Sau đó
for (i=0,i++,i<15)
for (j=0,j++,j<15)
if (a[i]==a[j]) a[j]=0;
for (i=0,i++,i<15)
if (a[i]!=0) printf(a[i],' ');

Cái này được viết theo ngôn ngữ lập trình nào đây?

[tara95]

Em nghĩ nếu bài này nếu không dùng mảng để lưu (giá trị chỉ xuất hiện 1 lần hoặc số lần xuất hiện của phần tử trong mảng) thì anh dùng 2 vòng lặp for, dùng biến đếm số phần tử giống nó xuất hiện trong mảng.

[11520537]

Em nghĩ nếu bài này nếu không dùng mảng để lưu (giá trị chỉ xuất hiện 1 lần hoặc số lần xuất hiện của phần tử trong mảng) thì anh dùng 2 vòng lặp for, dùng biến đếm số phần tử giống nó xuất hiện trong mảng.

Mình không hiểu đếm số phần tử nhau để làm gì? Bạn giải thích rõ hơn được không?

[tara95]

Mình không hiểu đếm số phần tử nhau để làm gì? Bạn giải thích rõ hơn được không?

Em hơi nhầm một tí.
Anh thử cách này xem: Duyệt hết các phần tử của mảng, phần tử được in ra thỏa mãn: trước nó không có phần tử nào giống nó, và sau nó có ít nhất 1 phần tử giống nó, tức là sẽ in phần tử xuất hiện đầu tiên.

[11520272]

Em hơi nhầm một tí.
Anh thử cách này xem: Duyệt hết các phần tử của mảng, phần tử được in ra thỏa mãn: trước nó không có phần tử nào giống nó, và sau nó có ít nhất 1 phần tử giống nó, tức là sẽ in phần tử xuất hiện đầu tiên.

Trường hợp này nó có thể có nhiều hơn 1 phần tử giống nó?

[11520031]

for (i=0,i<n,i++)
{
for (j=i,j<n,j++)
if (a[i]=a[j])
for (k=i-1,k--,k<0)
if (a[i]==a[k]) {check=false;break}
else check=true;
if (check=true) printf(a[i]);
}

[11520327]

Cách này hơi củ chuối, nhưng được cái là sử dụng 2 vòng for. Cách này lỗi khi trong mảng arr có phần tử nào đó là -1. Đưa lên đây để bàn luận thôi.

#include <iostream>
 
using namespace std;
 
int main()
{
   int arr[15] = {1, 2, 3, 4, 1, 6, 2, 3, 7, 1, 7, 1, 8, 4, 1};
   int n=15;
   int k=-1; // k is used to set for unchecked element
   for(int i=0; i<n-1; ++i){
       bool isExisted = false; // check if arr[i] appears more than 1
       if(arr[i]!=-1){  // do not check if arr[i] == -1
           for(int j=i+1; j<n; ++j){          
               if(arr[i]==arr[j]){
                   isExisted=true; // arr[i] appears more than 1
                   arr[j]=-1; // do not check arr[j] again in future
               }
           }
           if(isExisted==true){ // arr[i] appears more than 1
               cout<<arr[i]<<" ";
           }
       }
   }
   
   return 0;
}

[11520348]

Cách này hơi củ chuối, nhưng được cái là sử dụng 2 vòng for. Cách này lỗi khi trong mảng arr có phần tử nào đó là -1. Đưa lên đây để bàn luận thôi.

#include <iostream>
 
using namespace std;
 
int main()
{
   int arr[15] = {1, 2, 3, 4, 1, 6, 2, 3, 7, 1, 7, 1, 8, 4, 1};
   int n=15;
   int k=-1; // k is used to set for unchecked element
   for(int i=0; i<n-1; ++i){
       bool isExisted = false; // check if arr[i] appears more than 1
       if(arr[i]!=-1){  // do not check if arr[i] == -1
           for(int j=i+1; j<n; ++j){          
               if(arr[i]==arr[j]){
                   isExisted=true; // arr[i] appears more than 1
                   arr[j]=-1; // do not check arr[j] again in future
               }
           }
           if(isExisted==true){ // arr[i] appears more than 1
               cout<<arr[i]<<" ";
           }
       }
   }
   
   return 0;
}

Chủ thớt không muốn phá vỡ cái mảng. Muốn giữ nguyên hiện trạng ban đầu của mảng. :sogood:
Đảm bảo thế này thớt sẽ vào phản biện lại. :look_down:

[11520537]

Cách này hơi củ chuối, nhưng được cái là sử dụng 2 vòng for. Cách này lỗi khi trong mảng arr có phần tử nào đó là -1. Đưa lên đây để bàn luận thôi.

#include <iostream>
 
using namespace std;
 
int main()
{
   int arr[15] = {1, 2, 3, 4, 1, 6, 2, 3, 7, 1, 7, 1, 8, 4, 1};
   int n=15;
   int k=-1; // k is used to set for unchecked element
   for(int i=0; i<n-1; ++i){
       bool isExisted = false; // check if arr[i] appears more than 1
       if(arr[i]!=-1){  // do not check if arr[i] == -1
           for(int j=i+1; j<n; ++j){          
               if(arr[i]==arr[j]){
                   isExisted=true; // arr[i] appears more than 1
                   arr[j]=-1; // do not check arr[j] again in future
               }
           }
           if(isExisted==true){ // arr[i] appears more than 1
               cout<<arr[i]<<" ";
           }
       }
   }
   
   return 0;
}

Về cách củ chuối này thì mình cũng đã áp dụng với cách tương tự của bạn đó là mình gán 0 cho phần tử bị trùng.

[11520132]

Mình làm như này, không thay đổi mảng, không dùng mảng tạm không biết đáp ứng được không?

var arr = [1, 2, 3, 4, 1, 6, 2, 3, 7, 1, 7, 1, 8, 4, 1];
for (i = 0; i < arr.length; ++i) {
    for (j = 0; j < i && arr[i] != arr[j]; ++j);
    if (i == j) {
        for (++j; j < arr.length && arr[i] != arr[j]; ++j);
        if (j != arr.length) console.log(arr[i]);
    }
} 

[11520327]

Chủ thớt không muốn phá vỡ cái mảng. Muốn giữ nguyên hiện trạng ban đầu của mảng. :sogood:
Đảm bảo thế này thớt sẽ vào phản biện lại. :look_down:

Có t đây :love:. Có cách nào làm mà tối ưu k ta? Củ chuối nhưng dc cái chạy nhanh. Còn cái cách 3 vòng for thì không bàn ở đây. :doubt:

[11520148]

viết 2 hàm kiểm tra bool KiemTraTrung(int[] a, int n) và bool KiemTraDaIn(int[] a, int n, int index) là giải quết cả 2 câu

[11520132]

Có t đây :love:. Có cách nào làm mà tối ưu k ta? Củ chuối nhưng dc cái chạy nhanh. Còn cái cách 3 vòng for thì không bàn ở đây. :doubt:

Của mình 2 vòng for lồng nhau thôi mà. Mình viết bằng js, có thể viết lại như thế này cho ngắn, nhưng ngôn ngữ khác thì có thể hàm indexOf không hoạt động tương tự.

var arr = [1, 2, 3, 4, 1, 6, 2, 3, 7, 1, 7, 1, 8, 4, 1];
for (i = 0; i < arr.length; ++i)
    if (arr.indexOf(arr[i]) == i && arr.indexOf(arr[i],i+1) > 0)
        console.log(arr[i]);