Graveton
BAN USERThe code does not work for 9015, 901
You take the last digit from the shorter number of compare it with the suffix of the shorter string. But you should compare the prefix of shorter string after you get to the end of the shorter string: you compare the 5 to 1, instead you should compare 9 (from 901) to 5.
Wave: sort it, add half of the array when creating waves to avoid equal values close
public class WaveArrange {
public static int[] waveArrange(int[] input)
{
int[] result=new int[input.length];
int[] copiedInput=input.clone();
Arrays.sort(copiedInput);
int offset=input.length/2;
for (int i=0;i<input.length/2;i++)
{
result[2*i]=copiedInput[i+offset];
result[2*i+1]=copiedInput[i];
}
if (input.length%2==1)
{
result[input.length-1]=copiedInput[input.length-1];
}
return result;
}
}
@Test
public void testWaveArrange() throws Exception {
int[] input=new int[]{1,2,3};
int[] expected=new int[]{2,1,3};
assertArrayEquals(expected, WaveArrange.waveArrange(input));
input=new int[]{3,3,3,3,4,4,4,4};
expected=new int[]{4,3,4,3,4,3,4,3};
assertArrayEquals(expected, WaveArrange.waveArrange(input));
}
Sorting is not neccessary. Compute the distances, find the mth-nearest distance (can be done in linear, search for selection algorithm), then iterate all the points once again and return those with the smaller distance from the center than the m-th nearest. Only ties with m-th nearest must be handled specially but that is an easy one.
Total complexity O(n)
- Graveton November 21, 2015