In ra lần lượt các số trong dãy số mà chỉ xuất hiện đúng một lần, theo thứ tự xuất hiện

#1

Đề bài cũng như trên tiêu đề.
Mình có quay lại phần bài tập vòng lặp hồi trước để dùng unorder_map giải bài toán ấy. Nhưng code bị sai 2/4 test. Mong mọi người giúp chỉ ra vấn đề.
INPUT
10
1 3 4 2 1 3 4 5 6 7
OUTPUT
2 5 6 7

#include <bits/stdc++.h>
using namespace std;
unordered_map <int, int> hm;
int main()
{
    int n; cin >> n; int a[n];
    for(int i=0; i<n; i++)
    {
        cin >> a[i];
        hm[a[i]]++;
    }
    int *arr= new int, index=0;
    for(auto it=hm.begin(); it!=hm.end(); it++)
    {
        if(it->second==1)
        {
            arr[index++]=it->first;
        }
    }
    for(int i=index-1; i>=0; i--) cout << arr[i] << " ";
}
#2

Bạn đang bỏ qua yêu cầu

In ra lần lượt các số trong dãy số mà chỉ xuất hiện đúng một lần, theo thứ tự xuất hiện (của phần tử trên mảng a chứ không phải trên cái map!)

Phải chạy lại trên mảng a, nếu a[i] xuất hiện 1 lần thì in i ra.

3 Likes
#3

mình dùng unorder_map mà. mảng a với unorder_map thứ tự xuất hiện vẫn thế chỉ ngược nhau thôi chứ

#4

Nó không như bạn nghĩ đâu.

Mảng a được khai báo với không có phần tử nào, vậy thì arr[1], arr[2] nằm ở đâu?

4 Likes
#6

cái unorder_map thì mình hiểu rồi, còn cái arr thì theo mình nghĩ là cấp phát động cho nó.
rồi arr[1], arr[2] lần lượt gán giá trị là các key mà value==1 khi tìm thấy trong hm

#7

Cấp phát động không có số phần tử cụ thể thì có nghĩa lý gì đâu :penguin:

1 Like
#8

Hi vọng là bạn đã đọc kĩ đề.

2 Likes
#9

Người ta thường tránh việc duyệt qua hash map. Cấu trúc dữ liệu của hash map không phải để làm việc đó. Bài này bạn duyệt mảng lại lần 2 như @noname00 nói là được

2 Likes
#10

tại sao lại tránh duyệt qua hash map??? :V Nó y như in mảng 2 chiều thôi. CTDL hmap thế nào mà ko phải để duyệt qua tất cả các phần tử? :V

chắc là hiểu nhầm ý. Các phần tử trong hash map ko được sắp xếp theo thứ tự nào hết nên đừng duyệt và hy vọng là nó theo thứ tự được input vào. CTDL của unordered_map ko lưu dữ liệu theo thứ tự truyền vào. Một số hash map bảo đảm thứ tự insert vào cũng là thứ tự duyệt vào như OrderedDict bên Python, nhưng C++ unoreded map thì ko theo thứ tự cho vào.

4 Likes
#11

Hash map để tìm kiếm cho nhanh chứ ko phải để for trong đó :smiley:

#12

for trong unordered map cũng là O(n) như duyệt mảng thôi, hằng số có thể lớn hơn nhưng vẫn là O(n) có chậm hơn bao nhiêu đâu :V

int n; cin >> n;

vector<int> a(n); // thay cho int a[n]
for (int& x : a) cin >> x;

unordered_map<int, int> freq;
for (int x : a) freq[x]++;

for (int x : a) 
    if (freq[x] == 1) cout << x << " ";

xài map<int, int> cũng được, chậm quá thì mới sang unordered_map :V

2 Likes
#13

mình có đọc kĩ mà, vấn đề là ban đầu mình tưởng rằng unorder_map luôn giữ nguyên thứ tự các phần tử như khi nhâp. cái tên unorder làm mình chủ quan k tìm hiểu kĩ nó.

#14

nó ghi unordered nghĩa là ko có thứ tự rồi :V

2 Likes
#15

nhưng nó " but organized into buckets depending on their hash values to allow for fast access to individual elements directly by their key values"

#16

bao nhiêu chữ tiếng Anh đó? :V Sao ko đọc cái tên là nó la làng cảnh báo unordered ko có thứ tự rồi…

nó giống như mảng 2 chiều “răng cưa” ấy, mỗi bucket là 1 dòng trong mảng 2 chiều. Hash value của từng key sẽ xác định key đó nằm trong dòng thứ mấy. Ví dụ hmap có 10 bucket thì lấy hashvalue % 10. Như vậy 13 sẽ vào dòng 3, 7 vào dòng 7, vậy là 13 đứng trước 7, ko theo thứ tự lớn nhỏ, ko theo thứ tự truyền vào. Nếu số bucket là 16 thì 13 vào bucket thứ 13, 7 vào bucket thứ 7, 7 lại đứng trước 13…

3 Likes
#17

thì mình đồng ý là nó k có thứ tự nhất định nào mà, ý mình là nó k đc sắp xếp nhưng nó cũng sẽ khác so với thứ tự khi duyệt phần tử vào

#18

cách duyệt mảng 2 lần mình đã làm rồi

#19

Bởi vì việc duyệt hash map là không cần thiết. Khi hash map có search time là O(1). Một số hashing technique như perfect hashing đòi hỏi kích thước thực của hash map lớn hơn kích thước của data set (thực ra là hầu hết, chỉ trừ hashing with chaining)

#20

:V tại sao duyệt hash map là ko cần thiết??? Ví dụ tìm từ xuất hiện nhiều nhất trong 1 bài văn, duyệt từng từ cho vào hash map tăng số lần xuất hiện (ko chơi if else lưu từ xuất hiện nhiều nhất :V) , rồi làm cách nào để biết từ nào xuất hiện nhiều nhất? Ko phải là đi duyệt hash map à? Hay ví dụ cho 1 cái hash map, hỏi làm cách nào để biết key nào có value “to” nhất chẳng hạn, cũng phải duyệt hash map thôi :V

2 Likes
#21

Nhắc đến lớn nhất nhỏ nhất, so sánh, người ta build tree chứ không xài hash map. Bởi vì đó không phải là thế mạnh của hash map. Hash map chỉ mạnh ở tìm kiếm, insert, delete constant time. Tất nhiên chẳng ai cấm duyệt qua hash map, có thể có trường hợp đặc biệt nào bắt buộc(?). Nhưng đơn giản như trong bài thì duyệt qua cả hash map đơn giản là không cần thiết.

83% thành viên diễn đàn không hỏi bài tập, còn bạn thì sao?