Tìm các giá trị khác nhau trong mảng

[11520318]

Chào mọi người!
Có một đứa bạn hỏi mình một bài toán về mảng nhưng mình suy nghĩ mãi mà không ra nên mình muốn nhờ sự giúp đỡ của mọi người. Bài toán như sau:
Cho một mảng số nguyên lớn (khoảng 1 triệu phần tử), các giá trị trong mảng có thể lặp lại nhiều lần. Yêu cầu tìm và in ra tất cả khác giá trị khác nhau trong mảng (không cho phép sử dụng 2 vòng lặp lồng nhau).
Mới đầu thì mình làm theo phương pháp sắp xếp mảng tăng dần rồi sau đó duyệt mảng để in ra kết quả. Nhưng mà tất cả các thuật toán sắp xếp đều sử dụng 2 vòng lặp lồng nhau nên đến bây giờ mình vẫn chưa có cách để giải quyết bài này.
Mong mọi người giúp mình tìm lời giải.:salute:

[toannv]

Chào mọi người!
Có một đứa bạn hỏi mình một bài toán về mảng nhưng mình suy nghĩ mãi mà không ra nên mình muốn nhờ sự giúp đỡ của mọi người. Bài toán như sau:
Cho một mảng số nguyên lớn (khoảng 1 triệu phần tử), các giá trị trong mảng có thể lặp lại nhiều lần. Yêu cầu tìm và in ra tất cả khác giá trị khác nhau trong mảng (không cho phép sử dụng 2 vòng lặp lồng nhau).
Mới đầu thì mình làm theo phương pháp sắp xếp mảng tăng dần rồi sau đó duyệt mảng để in ra kết quả. Nhưng mà tất cả các thuật toán sắp xếp đều sử dụng 2 vòng lặp lồng nhau nên đến bây giờ mình vẫn chưa có cách để giải quyết bài này.
Mong mọi người giúp mình tìm lời giải.:salute:

Em dùng thuật toán đếm ở đây http://forum.uit.edu.vn/threads/5412...l=1#post321521 - 1 vòng lặp rồi sau đó in ra những số có SL > = 1

[truonganpn]

Chào mọi người!
Có một đứa bạn hỏi mình một bài toán về mảng nhưng mình suy nghĩ mãi mà không ra nên mình muốn nhờ sự giúp đỡ của mọi người. Bài toán như sau:
Cho một mảng số nguyên lớn (khoảng 1 triệu phần tử), các giá trị trong mảng có thể lặp lại nhiều lần. Yêu cầu tìm và in ra tất cả khác giá trị khác nhau trong mảng (không cho phép sử dụng 2 vòng lặp lồng nhau).
Mới đầu thì mình làm theo phương pháp sắp xếp mảng tăng dần rồi sau đó duyệt mảng để in ra kết quả. Nhưng mà tất cả các thuật toán sắp xếp đều sử dụng 2 vòng lặp lồng nhau nên đến bây giờ mình vẫn chưa có cách để giải quyết bài này.
Mong mọi người giúp mình tìm lời giải.:salute:

Nếu giá trị của mỗi phần tử là nhỏ thì em tham khảo link trên của thầy Toàn. Còn nếu giá trị các phần tử là lớn thì em nên ném nó vào một cái cây nhị phân tìm kiếm cân bằng hay một cái bảng băm em nhé.

[15520197]

Ủa? 1000.000 phần tử, mình dùng thuật toán sắp xếp nhanh chỉ với O(N*log(N)) thôi mà anh.
Với lại nếu dùng đếm phân phối thì phải tùy vào giới hạn của a[i] nữa.

[14520820]

Ủa? 1000.000 phần tử, mình dùng thuật toán sắp xếp nhanh chỉ với O(N*log(N)) thôi mà anh.
Với lại nếu dùng đếm phân phối thì phải tùy vào giới hạn của a[i] nữa.

sắp xếp nhanh thì không phù hợp yêu cầu đề rồi mà.

[12520167]

Ủa? 1000.000 phần tử, mình dùng thuật toán sắp xếp nhanh chỉ với O(N*log(N)) thôi mà anh.
Với lại nếu dùng đếm phân phối thì phải tùy vào giới hạn của a[i] nữa.

theo mình nghĩ thì nếu sort mảng xong thì cũng đâu có ra vân đề, còn phải xóa mấy cái giống nhau nữa mà. Lại tốn 1 vòng for

[15520197]

Sao lại không phù hợp với yêu cầu đề ra anh? Miễn độ phức tạp máy vẫn còn chạy được mà.

[15520197]

Sort mảng xong, cho chạy từ đầu đến cuối mảng vẫn đếm được số phần tử khác nhau chứ ạ! 1 vòng for nữa thì sao đâu? Độ phức tạp thuật toán vẫn có thể máy còn chạy được.

[14520820]

Sao lại không phù hợp với yêu cầu đề ra anh? Miễn độ phức tạp máy vẫn còn chạy được mà.

người đặt vấn đề có nhắc đến độ phức tạp đâu, người ta chỉ cho biết yêu cầu là: "(không cho phép sử dụng 2 vòng lặp lồng nhau)"

[10520067]

Thử cái này coi.(chưa Test)

public void InMang(int[] inputs)
{
var outputs = new List<int>();
foreach (var input in inputs)
{
if (!outputs.Contains(input))
{
outputs.Add(input);
}
}
foreach (var output in outputs)
{
Console.WriteLine(output);
}
}

[14520820]

public void InMang(int[] inputs)
{
var outputs = new List<int>();
foreach (var input in inputs)
{
if (!outputs.Contains(input))
{
outputs.Add(input);
}
}
foreach (var output in outputs)
{
Console.WriteLine(output);
}
}

foreach (var input in inputs)
{

if (!outputs.Contains(input))
{

outputs.Add(input);

}

}

anh chuyển vào thế này thì nhìn ngoài nó như 1 vòng lặp thôi, nhưng thực tế thì bên trong đâu chỉ đơn thuần là 1 vòng lặp đâu. rõ ràng là "if (!outputs.Contains(input))" có chứa vòng lặp mà.

[10520067]

foreach (var input in inputs)
{

if (!outputs.Contains(input))
{

outputs.Add(input);

}

}

anh chuyển vào thế này thì nhìn ngoài nó như 1 vòng lặp thôi, nhưng thực tế thì bên trong đâu chỉ đơn thuần là 1 vòng lặp đâu. rõ ràng là "if (!outputs.Contains(input))" có chứa vòng lặp mà.

Nói như em thì hàm so sánh chuỗi cũng có vòng lặp

[truonganpn]

Nói như em thì hàm so sánh chuỗi cũng có vòng lặp

Đề là mảng số nguyên mà chuỗi đâu ra em

[10520067]

Đề là mảng số nguyên mà chuỗi đâu ra em

ak. chưa hiểu ý rồi.
Ý là nếu hàm so sánh 2 chuỗi cũng được gọi là có vòng lặp trong trường hợp trên thì hàm contrains trên List cũng có vòng Lặp.
string a = "abc";
string b = "cde";
if (a.Contains(b))
{
return true;
}
như ví dụ trên thì được gọi là có vòng lặp không ?.

[14520820]

Nói như em thì hàm so sánh chuỗi cũng có vòng lặp

ak. chưa hiểu ý rồi.
Ý là nếu hàm so sánh 2 chuỗi cũng được gọi là có vòng lặp trong trường hợp trên thì hàm contrains trên List cũng có vòng Lặp.
string a = "abc";
string b = "cde";
if (a.Contains(b))
{
return true;
}
như ví dụ trên thì được gọi là có vòng lặp không ?.

ý của em là anh lưu nó trong list thì khi anh tìm kiếm một phần tử trong list anh sẽ tốn ít nhất một vòng lặp để xem nó có ở trong đó hay không.
cho dù với ý tưởng đó anh không dùng contains trong list của c# thì nó cũng phải tốn vòng lặp thôi.