Meandering array

Problem:

　　Given a non-negatve integer array (int[] nums), sort the array such that it's in the following order: largest, smallest, second largest, second smallest, ...

　　Could you solve this problem with constant extra space?

We all know quick sort in an array scenario consumes O(1) extra space, however, in the meandering array problem, if we use a two pointer approach and do not store the original numbers in another array, we might overwrite a number that is still needed later. What shall we do?

Here we play a trick to store 2 numbers in 1 entry. We find out maximum in the array, denoted with max, and define ceil::=max+1, for any entry we store num=num1+num2*ceil, then num%ceil is num1 and num/ceil.

With this approach we scan the array, if the current index is even, then add nums[right]%ceil*ceil to nums[i]; if current index i is odd, then add nums[left]%ceil*ceil to nums[i]. See the simulation below.

Finally, divide each entry with ceil:

[13, 2, 5, 4]

See the code below:

public static void meanderingArray(int[] nums) {
    Arrays.sort(nums);
    int left=0;
    int right=nums.length-1;
    int ceil=nums[right]+1;
    for(int i=0;i<nums.length;i++) {
        if(i%2==0) {
            nums[i]+=nums[right--]%ceil*ceil;
        } else {
            nums[i]+=nums[left++]%ceil*ceil;
        }
    }
    for(int i=0;i<nums.length-1;i++) {
        nums[i]/=ceil;
    }
}

• 还没有人评论，欢迎说说您的想法！

相关课程

基于 OpenVINO™ 的 AI 视觉应用基础课

55998 0元 限免

英特尔 OpenCV 初级认证课程

7677 0元 限免

英特尔® OpenVINO™工具套件初级课程

292956 0元 限免