Hi guys, i have 2 vector needed merge. How can I find min dictionary order of vector after merge.
ex : A = {2, 3} B = {4, 5}
one of satis way is : {2, 4, 5, 3}, opposite {3, 2, 4, 5}, {3, 2, 5, 4} is not.
# | User | Rating |
---|---|---|
1 | ecnerwala | 3648 |
2 | Benq | 3580 |
3 | orzdevinwang | 3570 |
4 | cnnfls_csy | 3569 |
5 | Geothermal | 3568 |
6 | tourist | 3565 |
7 | maroonrk | 3530 |
8 | Radewoosh | 3520 |
9 | Um_nik | 3481 |
10 | jiangly | 3467 |
# | User | Contrib. |
---|---|---|
1 | maomao90 | 174 |
2 | awoo | 164 |
3 | adamant | 163 |
4 | TheScrasse | 159 |
4 | nor | 159 |
6 | maroonrk | 156 |
7 | -is-this-fft- | 150 |
8 | SecondThread | 147 |
9 | orz | 146 |
10 | pajenegod | 145 |
Hi guys, i have 2 vector needed merge. How can I find min dictionary order of vector after merge.
ex : A = {2, 3} B = {4, 5}
one of satis way is : {2, 4, 5, 3}, opposite {3, 2, 4, 5}, {3, 2, 5, 4} is not.
Name |
---|
if you mean a queue , then it is mergesort isn't it
No in this case the vectors are sorted but they may not be. I think what he is asking is the lexicographically smallest merging where the relative order of each element from each vector doesn't change. Eg:- a = {5, 1}, b = {2, 6} the answer is {2, 5, 1, 6}
But wouldn't $$$[2,3]$$$ and $$$[4,5]$$$ result in $$$[2,3,4,5]$$$ then? I think OP needs to clarify this
yes, for sure. I was also confused on this, but he/she says "one of satis way is ..." hard to decode tbh :)
{2, 3, 4, 5} is the answer we need :v
The way to solve this is:
Think of the vectors as queues, and greedily pop from the queue with smaller front value.
But how to handle duplicates?
a concat b
a concat b
in O(1) which will tell us which queue to pop fromthank u, is it O(n)
bonus : {2, 3, 4, 5} is the answer of ex test cases
then maybe just do a greedy thing like having the tops out and compare and choose
how about hashing and binary search :v
Well, maybe binary search could work, but it doesn't make the solution any easier. There is a greedy two-pointers way to solve this problem in $$$O(n+m)$$$.
but when a[i] = b[j], which element should we get
advance both pointers until the two pointers point to a different character. choose the lexicographically smaller side (segment).
ex) assume we have two strings $$$\text{bbbbabbbbb}$$$ and $$$\text{bbbbcbbbbb}$$$. Now the first difference happens on $$$\text{a}$$$ and $$$\text{c}$$$, so you can append $$$\text{bbbba}$$$ to the answer, move the pointer on $$$\text{bbbbcbbbbb}$$$ to the previous position, and keep going. answer will be $$$\text{bbbbabbbbbbbbbcbbbbb}$$$.
tks u, it look like hash but complex O(n)
Is it SPOJ MINSEQ?