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

Góc học tập Thuật toán - Trí tuệ nhân tạo - Khoa học máy tính
1

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:

2

[QUOTE=11520318;322013]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:[/QUOTE]

Em dùng thuật toán đếm ở đây http://forum.uit.edu.vn/threads/54127-Huan-luyen-kien-thuc-ve-thuat-toan?p=321521&viewfull=1#post321521 - 1 vòng lặp rồi sau đó in ra những số có SL > = 1

3

[QUOTE=11520318;322013]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:[/QUOTE]

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

4

Ủa? 1000.000 phần tử, mình dùng thuật toán sắp xếp nhanh chỉ với O(Nlog(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 nữa.

5

[QUOTE=15520197;344014]Ủa? 1000.000 phần tử, mình dùng thuật toán sắp xếp nhanh chỉ với O(Nlog(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 nữa.[/QUOTE]
sắp xếp nhanh thì không phù hợp yêu cầu đề rồi mà.
:confused:

6

[QUOTE=15520197;344014]Ủa? 1000.000 phần tử, mình dùng thuật toán sắp xếp nhanh chỉ với O(Nlog(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 nữa.[/QUOTE]
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

7

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

8

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.

9

[QUOTE=15520197;344438]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à.[/QUOTE]

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)”

10

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

11

[QUOTE=10520067;344603]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);
}
}[/QUOTE]
foreach (var input in inputs)
{
[INDENT]if (!outputs.Contains(input))
{
[INDENT]outputs.Add(input);[/INDENT]
}[/INDENT]
}
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à.

12

[QUOTE=14520820;344728]foreach (var input in inputs)
{
[INDENT]if (!outputs.Contains(input))
{
[INDENT]outputs.Add(input);[/INDENT]
}[/INDENT]
}
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à.[/QUOTE]
Nói như em thì hàm so sánh chuỗi cũng có vòng lặp :slight_smile:

13

[QUOTE=10520067;344734]Nói như em thì hàm so sánh chuỗi cũng có vòng lặp :)[/QUOTE]
Đề là mảng số nguyên mà chuỗi đâu ra em

14

[QUOTE=truonganpn;344736]Đề là mảng số nguyên mà chuỗi đâu ra em[/QUOTE]

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

15

[QUOTE=10520067;344734]Nói như em thì hàm so sánh chuỗi cũng có vòng lặp :)[/QUOTE]
[QUOTE=10520067;344741]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 ?.[/QUOTE]

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

16

Nói như em thì chỉ với câu lệnh in ra màn hình dòng chữ hello word cũng chạy qua bao nhiêu vòng lặp trong hệ thống mới đưa ra được dòng chữ đó.
Ý anh ở đây là dùng contrains thì NGƯỜI LẬP TRÌNH sẽ không phải viết 2 dòng lệnh lặp nhau.
Chứ Define của contrains thì đương nhiên là sử dụng vòng lặp rồi.

17

[QUOTE=10520067;344755]Nói như em thì chỉ với câu lệnh in ra màn hình dòng chữ hello word cũng chạy qua bao nhiêu vòng lặp trong hệ thống mới đưa ra được dòng chữ đó.
Ý anh ở đây là dùng contrains thì NGƯỜI LẬP TRÌNH sẽ không phải viết 2 dòng lệnh lặp nhau.
Chứ Define của contrains thì đương nhiên là sử dụng vòng lặp rồi.[/QUOTE]

cái em muốn nói đến cái ý tưởng. chứ như các ngôn ngữ khác như C++ chẳng hạn. nó đâu có contains đó đâu. khi anh dùng list anh sẽ dùng stl rồi phương thức find của nó để tìm phần tử. nếu anh cứ lấy mấy cái dùng sẵn như vậy thì người ta hỏi câu hỏi trên kia làm gì đâu. chứ nếu cứ dùng cái dựng sẵn vậy sao người ta không dùng hàm sort+unique có sẵn rồi làm luôn cho khỏe.
hơn nữa có thể cái yêu cầu câu hỏi đó không muốn sử dụng vòng lặp lồng là để thỏa mãn yêu cầu nào đó thực tế thì sao. như muốn giảm độ phức tạp chẳng hạn. 1 triệu phần tử chằng hạn, anh dùng nhiều vòng lặp lồng đơn thuần thôi thì anh xem độ phức tạp bao nhiêu. thời gian xử lý nó sẽ ra sao. nếu còn mở rộng dữ liệu lớn hơn gấp nhiều nữa thì sao. nếu chỉ 1 vòng lặp với độ phức tạp O(n) nó sẽ rất khác biệt.
tóm lại theo em thì nếu mà người hỏi chỉ muốn thỏa mãn code mau lẹ vài dòng và không cần tính toán thì chắc cũng không đưa lên hỏi cách ở đây làm gì hết á.

18

Nếu Quicksort là 2 vòng lặp lồng nhau thì độ phức tạp đã quá giới hạn rồi anh. :smiley: