3 ms·
The both problems that you mentioned are quite similar, IMO
by coderfreak333 10y ago
The both problems that you mentioned are quite similar, IMO
- cousin_it 10y agoThe first has a simple solution if you know some university-level math. The second has no simple solution AFAIK.
- openasocket 10y agoI must be missing something, because problem 2 seems easy. It's just an array of boolean values, right? So you just pass over the array once, counting the number of zeroes. Then pass of the first n elements (for n the number of zeroes) and write zero to them, and write one to all the rest of the array. That's clearly stable (right?), requires only two passes over the array so it's O(N) time, and the only memory used is an index for looping and the count of the number of zeroes so it's O(1) memory. I'm guessing I'm missing something important, what is it?
- mkingston 10y agoSuppose you have a type A ('0' in the original description) and a type B ('1' in the original description). Suppose any instance of A < any instance of B, but any given instance of A is not necessarily even comparable to another instance of A. Similarly any instance of B is not necessarily comparable to another instance of B. Now stably sort an array containing instances of A and B.
- openasocket 10y agoOK, now I see why this is hard, thanks. Now I'm gonna spend the next few days mulling over this problem :) I noticed the problem is relatively easy if you're dealing with a linked list instead of an array, because you can easily move elements around. If there's some way to amortize that in the array case...
- cousin_it 10y agoA linked list has O(n) extra space to play with, compared to an array, so of course everything is easier. You can't transfer algorithms from one to the other.
- deleted 10y ago[deleted]