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

[11520132]

Em năm nhất, đang học mảng, bon chen tý, đang bí bài " nhhập vào mảng, liệt kê tần suất xuất hiện các phần tử trong mảng, moi phần tử liêt kê 1 lần", dự là sẽ xắp xếp tăng dần trước nếu a[i]<[ai+1] thì mới sử lý đếm vậy là ko bị trùng.....em viết code bị lặp vô tận, anh nào giúp voi, thân

void HoanVi(int &a, int &b)
{
    int temp = a;
    a = b;
    b = temp;
}
void BubleSort(int A[], int n)
{
    for (int i = 0; i<n - 1; i++)
    for (int j = n - 1; j>i; j--)
    if (A[j]<A[j - 1])
        HoanVi(A[j], A[j - 1]);
}
void tansuat(int a[], int n)
{
    int dem = 0;
    int tam ;
    BubleSort(a, n);
    for (int i = 0; i < n;i++)
    {
        if (a[i] < a[i + 1])
        {
            tam = a[i];
            for (int j = 0; j < n; j++)
            if (a[j] == tam)
                dem++;
            printf("%d\t", tam);
            printf("%d\n", dem);
        }
    }
} 

Cái này anh viết bằng js em có thể tham khảo thuật toán, không cần sắp xếp lại. Chỉ chạy 2 vòng lặp lồng nhau. C vs JS cú pháp cũng không khác lắm đâu. Anh lấy luôn cái mảng của thread.

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; ++j){ //Kiểm tra xem phần tử thứ i có phải là lần đầu tiên xuất hiện hay không
        if (arr[i] == arr[j]) break;  //Kiểm tra xem phần tử trước phần tử thứ i có phần tử nào = phần tử thứ i không
    }
    if (i == j) { //Nếu không có phần tử nào trước phần tử thứ i có giá trị bằng phần tử thứ i -> lần đầu tiên xuất hiện trong mảng
        var count = 1; // Khai báo bộ đếm ban đầu bằng 1
        for (++j; j < arr.length; ++j){ // Đếm từ phần tử thứ i+1 trở đi những phần thử bằng phần tử thứ i
            if (arr[i] == arr[j]) ++count; // Tăng bộ đếm
        }
        console.log(arr[i] + ' - ' + count); // Print
    }
} 

Hoặc viết ngắn gọn lại thành:

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) {
        var count = 1;
        for (++j; j < arr.length && (arr[i] != arr[j] || ++count); ++j);
        console.log(arr[i] + ' - ' + count);
    }
} 

Kết quả:

1 - 5
2 - 2
3 - 2
4 - 2
6 - 1
7 - 2
8 - 1

[14520769]

Em năm nhất, đang học mảng, bon chen tý, đang bí bài " nhhập vào mảng, liệt kê tần suất xuất hiện các phần tử trong mảng, moi phần tử liêt kê 1 lần", dự là sẽ xắp xếp tăng dần trước nếu a[i]<[ai+1] thì mới sử lý đếm vậy là ko bị trùng.....em viết code bị lặp vô tận, anh nào giúp voi, thân
void HoanVi(int &a, int &b)
{
int temp = a;
a = b;
b = temp;
}
void BubleSort(int A[], int n)
{
for (int i = 0; i<n - 1; i++)
for (int j = n - 1; j>i; j--)
if (A[j]<A[j - 1])
HoanVi(A[j], A[j - 1]);
}
void tansuat(int a[], int n)
{
int dem = 0;
int tam ;
BubleSort(a, n);
for (int i = 0; i < n;i++)
{
if (a[i] < a[i + 1])
{
tam = a[i];
for (int j = 0; j < n; j++)
if (a[j] == tam)
dem++;
printf("%d\t", tam);
printf("%d\n", dem);
}
}
}

Cái "int dem=0;" bạn để trong vòng for (int i = 0; i < n;i++) thì ok

[11520327]

ý anh là tìm cách tối ưu mà không cần phải dùng thêm bất cứ mảng phụ nào hay sao.
- nếu dùng thêm mảng phụ. chỉ cần một mảng đánh dấu. sẽ duyệt được trong 2*O(n) với điều kiện các phần tử trong dãy đủ nhỏ(không quá 10^6)
-còn nếu ko cùng bất cứ mảng phụ nào thì duyệt trong O(n^2). với mỗi phần tử đã duyệt thì loại bỏ phần tử đó bằng cách gán cho nó một giá trị chắc chắc ko thuộc trong dãy.

Không dùng mảng phụ --> Loại cách 1.
Cách 2: đã có lời giải trong những # trước.
Bài của 10520100 khá hay, e nên tham khảo.

[13520211]

ý anh là tìm cách tối ưu mà không cần phải dùng thêm bất cứ mảng phụ nào hay sao.
- nếu dùng thêm mảng phụ. chỉ cần một mảng đánh dấu. sẽ duyệt được trong 2*O(n) với điều kiện các phần tử trong dãy đủ nhỏ(không quá 10^6)
-còn nếu ko cùng bất cứ mảng phụ nào thì duyệt trong O(n^2). với mỗi phần tử đã duyệt thì loại bỏ phần tử đó bằng cách gán cho nó một giá trị chắc chắc ko thuộc trong dãy.

[11520327]

[MENTION=12722]11520537[/MENTION]
@All

Mình có cách này, mọi người xem thử.

Ý tưởng của giải thuật sử dụng 1 mảng để đánh dấu số nào xuất hiện hay chưa. Tuy nhiên, thay vì cấp phát mảng, ta sử dụng một số nguyên. Khi nhìn nó dưới dạng một chuỗi bit 10101010010000 ta sẽ có được cách đánh dấu mảng dựa vào 1 số.

Giới hạn của đoạn code này là các số giới hạn trong khoảng [-32, 32]. Nếu muốn thuật toán làm việc với số lớn hơn thì phải extend kiểu dữ liệu.

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

bool isDuplicated(int sum, int x){
    //
    // Dieu kien sum >= 0 va x >= 0
    // Kiem tra xem, bit thu x co duoc bat hay chua
    // Neu bit thu x da duoc bat thi tra ve true
    // Neu bit thu x chua duoc bat thi tra ve false
    //
    return (sum & ( 1 << x ) );
}

int main(){

    //
    // Khoi tao
    //
    int arr[19] = {1, 2, 3, 4, 1, -2, -3, 6, 2, 3, 7, 1, 7, 1, 8, 4, 1, -2, -3};
    int length = sizeof(arr) / sizeof(*arr);
    int positiveSum = 0;
    int negativeSum = 0;
    
    
    //
    // Duyet va in ket qua
    //
    for(int counter = 0 ; counter < length ; ++ counter )
        if( arr[counter] > 0 ){
            //
            // Neu arr[counter] la so duong
            // Ta se dung positiveSum de kiem tra xem arr[counter] da xuat hien hay chua
            // Neu da xuat hien thi bo qua
            // Neu chua thi cong vao sum, va in ra man hinh
            //
            if(isDuplicated(positiveSum, arr[counter]) == false){
                positiveSum = positiveSum + (1 << arr[counter]);
                cout << arr[counter] << endl;
            }
        }
        else{
            //
            // Neu arr[counter] la so am
            // Ta se su dung negativeSum de kiem tra
            // Hoan toan tuong tu voi positiveSum, nhung danh cho so am
            //
            if(isDuplicated(negativeSum, - arr[counter]) == false){
                negativeSum = negativeSum + (1 << (- arr[counter]) );
                cout << arr[counter] << endl;
            }
        }
    
    
    //
    // Tra ve ket qua chuong trinh chay thanh cong
    //
    return 0;
} 

Sau 1 hồi nghiền ngẫm thì đã hiểu ra cách giải. Mỗi số trong mảng sẽ được đánh dấu bằng 1 bit trong positiveSum hoặc negativeSum. Do chỉ dùng 1 bit để đánh dấu 1 số và đảm bảo 2 số khác nhau không trùng bit đánh dấu, ta cần chuyển số cần đánh dấu về dạng lũy thừa của 2. Giả sử số cần đánh dấu là 3: ta sẽ chuyển 3 thành 2 mũ 3 = 8 và số 8 là lũy thừa của 2 nên có thể sử dụng 1 bit để dánh dấu trong positiveSum bằng cách lấy positiveSum + 8....

[10520100]

[MENTION=12722]11520537[/MENTION]
@All

Mình có cách này, mọi người xem thử.

Ý tưởng của giải thuật sử dụng 1 mảng để đánh dấu số nào xuất hiện hay chưa. Tuy nhiên, thay vì cấp phát mảng, ta sử dụng một số nguyên. Khi nhìn nó dưới dạng một chuỗi bit 10101010010000 ta sẽ có được cách đánh dấu mảng dựa vào 1 số.

Giới hạn của đoạn code này là các số giới hạn trong khoảng [-32, 32]. Nếu muốn thuật toán làm việc với số lớn hơn thì phải extend kiểu dữ liệu.

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

bool isDuplicated(int sum, int x){
    //
    // Dieu kien sum >= 0 va x >= 0
    // Kiem tra xem, bit thu x co duoc bat hay chua
    // Neu bit thu x da duoc bat thi tra ve true
    // Neu bit thu x chua duoc bat thi tra ve false
    //
    return (sum & ( 1 << x ) );
}

int main(){

    //
    // Khoi tao
    //
    int arr[19] = {1, 2, 3, 4, 1, -2, -3, 6, 2, 3, 7, 1, 7, 1, 8, 4, 1, -2, -3};
    int length = sizeof(arr) / sizeof(*arr);
    int positiveSum = 0;
    int negativeSum = 0;
    
    
    //
    // Duyet va in ket qua
    //
    for(int counter = 0 ; counter < length ; ++ counter )
        if( arr[counter] > 0 ){
            //
            // Neu arr[counter] la so duong
            // Ta se dung positiveSum de kiem tra xem arr[counter] da xuat hien hay chua
            // Neu da xuat hien thi bo qua
            // Neu chua thi cong vao sum, va in ra man hinh
            //
            if(isDuplicated(positiveSum, arr[counter]) == false){
                positiveSum = positiveSum + (1 << arr[counter]);
                cout << arr[counter] << endl;
            }
        }
        else{
            //
            // Neu arr[counter] la so am
            // Ta se su dung negativeSum de kiem tra
            // Hoan toan tuong tu voi positiveSum, nhung danh cho so am
            //
            if(isDuplicated(negativeSum, - arr[counter]) == false){
                negativeSum = negativeSum + (1 << (- arr[counter]) );
                cout << arr[counter] << endl;
            }
        }
    
    
    //
    // Tra ve ket qua chuong trinh chay thanh cong
    //
    return 0;
} 

[11520327]

Lâu lâu dạo forum, anh có cách này chia sẻ chứ không em cứ nghĩ cách của em là tối ưu nữa.

Code đó của bạn 14520674, không phải của em, em chỉ đánh giá thoi.

[13520939]

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],' ');

thế trường hợp có phần từ 0 trong mảng thì sao? Vấn đề xuất hiện

[14520183]

xem cái picture cho dễ nha mọi người
code.jpg

[14520183]

Mọi người ngó qua đoạn code của em phát. Em năm 1 trình độ nhập môn lập trình ạ ^^

#include <stdio.h>
#include <conio.h>

void main()
{
int a[15] = { 1, 2, 3, 4, 1, 6, 2, 3, 7, 1, 7, 1, 8, 4, 1 };
for (int i = 0; i <= 14; i++)
{
int out = 0;
for (int j = 0; (j <= 14); j++)
{
if (j == i)
continue;
else
if (a[j] == a[i])
if (j < i)
break;
else
out = 1;

}
if (out == 1)
printf("%3d", a[i]);
}
getch();
}

[08520021]

Ngồi buồn cắn móng tay

ex = [1, 2, 3, 4, 1, 6, 2, 3, 7, 1, 7, 1, 8, 4, 1]

def unduplicate(arr):
    checker = 0
    occurred = 0
    length = len(arr)
    
    for i in range(length):
        checker |= 1 << i
        
        for l in range(i + 1, length):
            if (not(checker >> l) % 2) and (arr[l] == arr[i]):
                checker |= 1 << l
                if not occurred:
                    print arr[i]
                    occurred = 1
                    
        occurred = 0

unduplicate(ex)

Array lớn thì đành chịu

[truonganpn]

Lâu lâu dạo forum, anh có cách này chia sẻ chứ không em cứ nghĩ cách của em là tối ưu nữa.
Với trường hợp này, nếu các phần tử ai giới hạn bé hơn khoảng 10^8 (vì lớn hơn có thể mảng không chứa nổi) thì mình có thể tạo một mảng đánh dấu. Các phần tử sẽ có 3 trạng thái là đã in, xuất hiện lần đầu, và trạng thái còn lại. Như vậy độ phức tạp chỉ là O(n) thôi.

Nếu ai lớn hơn 10^8 thì các bạn có thể sử dụng cấu dữ liệu vào để giảm độ phức tạp, ví dụ cây nhị phân, hoặc đại loại nhị phân để giảm còn O(nLog) Trong C++ có cấu trúc map, các bạn có thể dùng.

Ban đầu bạn chủ thớt nói là không muốn dùng thêm mảng phụ mà Có thể bạn ấy không nghĩ đến mảng đánh dấu hay một cấu trúc dữ liệu khác nhưng tui nghĩ về bản chất thì chữ "mảng phụ" nó cũng ám chỉ đến vấn đề space/time trade-off thôi. Không dùng thêm bộ nhớ (dù là ở dạng mảng phụ, mảng đánh dấu hay một cấu trúc dữ liệu khác) thì chắc chắn thuật toán sẽ phải chạy lâu hơn.

[10520355]

#include <iostream>
 
using namespace std;
 
int main()
{
   int a[15] = {1, 2, 3, 4, 1, 6, 2, 3, 7, 1, 7, 1, 8, 4, 1};
   int n=15;
   for(int i=0;i<n;i++)
    {
        int mark=-1;
        for(int j=0;j<n;j++)
            if (a[i]==a[j]&& i!=j) 
                mark=j;
        if(mark<i && mark !=-1)
            cout<< a[i] <<" ";
    }
   
   return 0;
}

2 for, cho kết quả đúng, không thay đổi cấu trúc mảng. O(n2). Có lẽ là lời giải hợp lí tới hiện tại.

Lâu lâu dạo forum, anh có cách này chia sẻ chứ không em cứ nghĩ cách của em là tối ưu nữa.
Với trường hợp này, nếu các phần tử ai giới hạn bé hơn khoảng 10^8 (vì lớn hơn có thể mảng không chứa nổi) thì mình có thể tạo một mảng đánh dấu. Các phần tử sẽ có 3 trạng thái là đã in, xuất hiện lần đầu, và trạng thái còn lại. Như vậy độ phức tạp chỉ là O(n) thôi.

nội dung file input.txt:
15
1 2 3 4 1 6 2 3 7 1 7 1 8 4 1

source
#include <iostream>
#include <cstdio>
using namespace std;
char arr[100000001];
int n,x;
int main() {
    freopen("input.txt","r",stdin);
    memset(arr,0,sizeof(arr));
    cin>>n;
    while(n--){
        cin>>x;
        arr[x]++;
        if(arr[x]==0) arr[x]--;
        else if(arr[x]>1) arr[x]=-1, cout<<x<<" ";
    }
    return 0;
} 

Nếu ai lớn hơn 10^8 thì các bạn có thể sử dụng cấu dữ liệu vào để giảm độ phức tạp, ví dụ cây nhị phân, hoặc đại loại nhị phân để giảm còn O(nLog) Trong C++ có cấu trúc map, các bạn có thể dùng.

nội dung file input.txt:
15
1 2 3 4 1 6 2 3 7 1 7 1 8 4 1

source code với ai trong kiểu long long int (2^63 -1)
#include <iostream>
#include <cstdio>
#include <map>
using namespace std;
typedef long long int ll;
int n,x;
map<ll, int> mm;
int main() {
    freopen("input.txt","r",stdin);
    cin>>n;
    while(n--){
        cin>>x;
        mm[x]++;
        if(mm[x]==0) mm[x]--;
        else if(mm[x]>1) mm[x]=-1,cout<<x<<" ";
    }
    return 0;
} 

code trên anh dùng nhập xuất từ file muốn nhập xuất từ console thì bỏ dòng freopen("input.txt","r",stdin); đi nha.

[11520327]

Mọi người thử thuật toán củ chuối với 2 vòng for này của mình xem

#include <iostream>
 
using namespace std;
 
int main()
{
   int a[15] = {1, 2, 3, 4, 1, 6, 2, 3, 7, 1, 7, 1, 8, 4, 1};
   int n=15;
   for(int i=0;i<n;i++)
    {
        int mark=-1;
        for(int j=0;j<n;j++)
            if (a[i]==a[j]&& i!=j) 
                mark=j;
        if(mark<i && mark !=-1)
            cout<< a[i] <<" ";
    }
   
   return 0;
}

2 for, cho kết quả đúng, không thay đổi cấu trúc mảng. O(n2). Có lẽ là lời giải hợp lí tới hiện tại.

[14520674]

Mọi người thử thuật toán củ chuối với 2 vòng for này của mình xem

#include <iostream>
using namespace std;
int main()
{
int a[100],n,i,j,mark;
{
// Nhap mang ...
}
// Xử lí
for(i=0;i<n;i++)
{
mark=-1;
for(j=0;j<n;j++)
if (a[i]==a[j]&& i!=j) mark=j;
if(mark<i && mark !=-1)
cout<< a[i] <<" ";
}
}