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

[11520327]

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

arr.IndexOf nó hoạt động bên dưới như thế nào chắc b cũng biết mà. Cơ bản thì cũng như b viết vòng for thôi. Tính ra thì cũng 3 for.

[11520348]

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:

Sort mảng xong là thấy cách làm rồi. :shy:

[11520327]

Sort mảng xong là thấy cách làm rồi. :shy:

Sort xong phải duyệt thêm lần nữa mà thánh.

[11520132]

arr.IndexOf nó hoạt động bên dưới như thế nào chắc b cũng biết mà. Cơ bản thì cũng như b viết vòng for thôi. Tính ra thì cũng 3 for.

Làm sao ra ba vòng lồng nhau được nhỉ, cái index đầu nó chỉ chạy tới i, cái index sau nó chạy từ i+1 tới length, vậy maximum là 2 vòng lồng nhau thôi chứ, nó tương đương với
for (i=0;i<arr.length;++i) for (j=0;j<arr.lenght;++j) thôi => O(n2)

[14520214]

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);
}
}
}

[12520332]

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);
}
}
}

Bạn để code trong thẻ thì mọi người mới giúp được nhé !

[tara95]

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

Em đang nêu ra điều kiện để phần tử được in ra thỏa "Xuất hiện nhiều hơn 1 lần và không được in trùng". "Có ít nhất 1 phần tử giống nó (>=1)" thì đã bao gồm "có nhiều hơn 1 phần tử giống nó (>1)". Em không hiểu ý anh lắm?

[tara95]

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

#include <stdio.h>

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);
        }
    }
}

int main()
{
    int arr[15] = {1, 2, 3, 4, 1, 6, 2, 3, 7, 1, 7, 1, 8, 4, 1};
    tansuat(arr,15);
    return 0;
}

Anh chạy tốt mà, nhưng sai kết quả. Em chạy lại và xem kết quả thử xem.

[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] <<" ";
}
}

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

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

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

[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

[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();
}

[14520183]

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