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

[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

[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.

[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]

[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....

[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]

ý 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.

[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

[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