Mọi người giúp e thuật toán bài này với:
Cho dãy số không âm có độ dài n. Đếm số các phàn tử xuất hiện từ 2 lần trở lên.
INPUT: Dòng đầu tiên ghi số n(n<=10^5), dòng tiếp theo là các phần tử trong dãy, 2 số liên tiếp cách nhau một dấu cách(Trị tuyệt đối các phần tư trong dãy không vượt quá 100).
OUTPUT: In ra một số duy nhất là số các phần tử xuất hiện từ hai lần trở lên.
Đếm số số xuất hiện từ hai lần trở lên
Có vài cách. Tôi chỉ gợi ý, bạn phải viết code nhé:
- Cách đơn giản nhất và cũng là cách tồi nhất (Giả sử rằng dãy chứa các phần tử là tên là arr):
Với mỗi phần tử thứ i trong arr:
So sánh với tất cả các phần tử còn lại trong arr
Nếu có phần tử giống như vậy: arr[i] là phần tử lặp lại
Cách này kém hiệu quả nhât vì phải dùng hai vòng lặp (O(n^2))
- Cách tốt hơn:
Với mỗi phần tử thứ i trong arr :
Nếu arr[abs(arr[i])] > 0
arr[abs(arr[i])] = -arr[abs(arr[i])]
Ngược lại
arr[i] là phần tử lặp lại
Bạn hãy tự tìm hiểu tại sao thuật toán này lại giải quyết được vấn đề nhé! Lưu ý là trong thuật toán này, tôi chưa giải quyết trường hợp arr[abs(arr[i])] == 0, bạn có thể xem như một bài tập nhỏ. Nó tốt hơn thuật toán đầu tiên vì chỉ dùng một vòng lặp hay O(n).
- Dùng hash table (hay hash set):
Tạo hashtable ht
Với mỗi giá trị thứ i trong arr
x = hash(arr[i])
Nếu ht có chứa x
arr[i] là phần tử lặp lại
Ngược lại
ht[x] = x
Thuật toán này cũng có thời gian chạy tương đương với thuật toán thứ hai vì chỉ dùng một vòng lặp (O(n))
Còn làm thế nào để đưa các phần tử từ file vào arr là việc của bạn nhé 
6 Likes
Sort lại đi bạn 
là ra thôi. (bài này thì ko sort thêm mảng 100 slot là đc)
4 Likes
Đề có cho trị tuyệt đối của phần tử nhỏ hơn 100 và dãy số không âm nữa thì dùng thuật toán “đưa bò vào chuồng” là dễ ăn nhất (tự search google nhé)
3 Likes
Xin bác chỉ giáo cách số 2, vì mình xem nãy giờ mà vẫn chưa hiểu cách nó hoạt động như thế nào. Hoặc có thể bác nhầm lẫn chỗ nào đó.
1 Like
Bạn cứ thử viết chương trình và theo dõi các giá trị của dãy (hoặc debug trên giấy cũng được) là sẽ thấy. Nếu vẫn chưa hiểu thì có thể nhắn cho tôi, tôi sẽ giải thích cho. Tôi không giải thích ở đây vì đây là bài tập cho bạn An Nguyễn.
Lưu ý là nó chỉ áp dụng với các phần tử > 0 (đó là lý do tôi nói còn lại trường hợp = 0 chưa xử lý).
3 Likes
Cách 2 có vẻ lạ thật, anh có thể chỉ giáo em thêm không.
Ví dụ với testcase thế này:
2
99 1
Nếu dùng cách 2, thì n = 2 và mảng arr gồm 2 phần tử là 99 và 1.
int n = 2;
int arr[] = { 99, 1 };
Lúc đó ở vòng for đầu tiên nó sẽ tính ra kiểu
arr[abs(arr[0])] = arr[abs(99)] = arr[99]
Cái phần truy xuất arr[99] này nằm ngoài mảng arr, có thể bị error luôn.
6 Likes
Bạn có thể khai báo dãy có 100 phần tử để tránh trường hợp index out of range (đó là lý do vì sao đề bài cho trị tuyệt đối của các phần tử không quá 100) và gán cho các phần tử không nằm trong file ban đầu giá trị dương bất kỳ - 1 chẳng hạn. Còn xét thì chỉ cần xét số các phần tử trong file mà thôi (Thật ra khi tôi dùng mệnh đề với mỗi giá trị thứ i trong arr thì cũng chưa chính xác lắm. Đúng ra phải là với mỗi giá trị thứ i trong trong arr với 0 <= i < số phần tử ban đầu trong file). Còn về giải thuật thật sự thì thật ra không có gì khó: chúng ta dùng index và dấu của phần tử arr[i] để đánh dấu một số đã xuất hiện hay chưa. Ví dụ như arr[k] = -x với x > 0 thì có nghĩa là số k đã có xuất hiện trước đó trong dãy. Giá trị của x không quan trọng. Bật mí thế nhé!
5 Likes
Em nghĩ nên tách riêng 1 mảng gồm 101 phần từ (từ 0,1,2,…,100) để đánh dấu thôi.
Cho arr làm 2 nhiệm vụ (lưu trữ input, đánh dấu) làm e hơi khó hiểu. 
Còn khai báo arr cố định 100 phần tử e thấy hơi sai sai, vì n có giới hạn trên đến 105 lận. 
6 Likes
Vẫn giải quyết được thôi bạn (tôi nói khai báo 100 phần tử là cho trường hợp bạn đưa ra). Vấn đề chính ở đây là nếu dùng hai array thì không tối ưu về không gian lưu trữ (Nếu dãy ban đầu có số phần tử lớn quá thì sao?). Tôi chỉ đưa ra giải thuật tổng quát còn các chi tiết thì để người hỏi giải quyết chứ
4 Likes
Số không quá 100 bạn
3 Likes
83% thành viên diễn đàn không hỏi bài tập, còn bạn thì sao?