lrafagnin
BAN USERThis is the best I got keeping the space on O(1) and O(n) without zeros
Wasn't sure by the description if the array has zeros in it so added code to handle but not without extra time
<script>
var arr = [100, -1, 5, 4, -7, 11, 12, 0, -2, -1, -10, 11, -2];
function sortNegative(arr) {
var negPos=-1;
var hasZero = false;
i=0;
while (i<arr.length) {
if (arr[i] < 0) {
tmp = arr[i];
negPos++;
//move all positives forward
for (j=i; j>negPos; j--) {
arr[j] = arr[j-1];
}
arr[negPos] = tmp;
}
if (arr[i] == 0)
hasZero = true;
i++;
}
if (hasZero) {
i=negPos;
while (i<arr.length) {
if (arr[i] == 0) {
tmp = arr[i];
negPos++;
//move all positives forward
for (j=i; j>negPos; j--) {
arr[j] = arr[j-1];
}
arr[negPos] = tmp;
}
i++;
}
}
return arr;
}
document.write(arr + '<br>');
document.write(sortNegative(arr));
</script>
My take on this
1. we need to arrange the numbers based on the index difference given
{3,2,1}->{0,1,1} means
{3} has none taller in front, {2} has 1 taller, {1} has 1 taller
so {3}>{1}>{2} or (3 greater than 1 greater than 2)
2. {5,4,3,2,1}->{0,0,0,0,0} means
{5} has none taller in front, {4} has none taller in front, {3} has none taller in front, ...
so {1}>{2}>{3}>{4}>{5}
3. {5,4,3,2,1}->{0,1,2,3,4} means
{5}>{4}>{3}>{2}>{1}
4. looking at the options above we can easily build an iteration to move the person to the index on the second array, taken the example {3,2,1}->{0,1,1}, steps are
-move {3} to position 0 - nothing to do
-move {2} to position 1 - nothing to do
-move {1} to position 1 - move {1} to position 1, {2} will need to move 1 position down
algorithm is quite simple
Below should be true
- lrafagnin August 31, 2013