Patrick
BAN USERYour algorithm seems (again, I might be misunderstanding) to use a lookback, and since you didn't mention starting params I assume you'd go with the beginning, and assign B[i] to the value found for A[i]. I was just confused because you didn't describe the initialization or mapping between B and A. For example, with the array:
{5,1,3,4,2,7} with k=3, the output I understand from your algo would be {5, 1, 1, 1,2,2}, where the intended output is {1,1,2,2}. It's a small bug, in that you add on k-1 elements to the beginning. If I missed some part where you pre-process k-1 elements then begin to copy to B (or another way of handling this) then I take it all back. :)
Does that make sense?
Assumptions:
Assume the problem is referring to a 1-indexed array (implementation could be 0 indexed, but the "first" spot is odd)
There are the floor[Length/2] even numbers and ceiling[length/2] odd numbers (so every number has a place).
By "order of numbers should not change", I'll take that to mean that if Ai and Ak are both odd or both even and i < k in the original, then Ai will be before Ak in the final output. I.e the order of odds and evens are maintained separately.
Algo:
Two pointers. OddPtr starts at 1, EvenPtr at 2
"Good" check for OddPtr => Arr[OddPtr] % 2 = 1
"Good" check for EvenPtr => Arr[EvenPtr] % 2 = 0
If they're both wrong, switch and go to finishing step.
If OddPtr is wrong, move to EvenPtr + 1 and check if good. If so, walk the value and pointer back to original position of OddPtr (swap all elements down along the way, instead of direct swap). If EvenPtr + 1 not odd, OddPtr++ and try again.
If EvenPtr is wrong, EvenPtr++ and check. Do the same thing as OddPtr.
Finishing: Add two to OddPtr and EvenPtr, until EvenPtr > Arr.Length().
Walkthrough:
() = OddPtr
[] = EvenPtr
Initial array: 2,4,1,3,5,7,6,8
Step 1: (2),[4],1,3,5,7,6,8 => OddPtr is wrong. Go to EvenPtr+1=> 2,[4],(1),3,5,7,6,8. Valid, walk 1 and OddPtr back (EvenPtr stays at pos2), giving (1),[2],4,3,5,7,6,8. Move pointers
Step 2: 1,2,(4),[3],5,7,6,8 => Both wrong, swap & finish.
Step 3: 1,2,3,4,(5),[7],6,8 => EvenPtr wrong. Move up one. 6 is even, so walk it back & finish.
Step 4: 1,2,3,4,5,6,(7),[8] => Good. Finish, which hits terminal condition, done.
Code:
inline bool CheckOdd(int n) { return (n % 2 == 1); }
inline bool CheckEven(int n){ return (n % 2 == 0); }
inline void Swap(int *arr, int ptr1, int ptr2) { int temp = arr[ptr1]; arr[ptr1] = arr[ptr2]; arr[ptr2] = temp }
public int* ShuffleOddsAndEvens (int* arr, int arrLength)
{
int OddPtr = 0;
int EvenPtr = 1;
while(EvenPtr < arrLength)
{
if( !CheckOdd(arr[OddPtr]) && !CheckEven(arr[EvenPtr])) { swap(arr, OddPtr, EvenPtr); }
else if( !CheckOdd(arr[OddPtr])
{
int originalOddPtr = OddPtr;
OddPtr = EvenPtr + 1;
while(OddPtr < arrLength && !CheckOdd(arr[OddPtr]))
{
OddPtr++;
}
while(OddPtr > originalOddPtr)
{
swap(arr, OddPtr, OddPtr-1);
OddPtr--;
}
}
else if (!CheckEven(arr[EvenPtr]))
{
//Same as above, just Even
}
OddPtr += 2;
EvenPtr += 2
}
return arr;
}
Not sure if the code is 100%, but the algo should work
- Patrick September 17, 2012
Ah, gotcha, very nice. The initialization and the placing minimum calculated at a[i+k-1] into a[i] wasn't clear to me. Thanks!
- Patrick September 17, 2012