c++ O(n) solution with a simple proof


  • 0
    A

    I have no idea when I first saw this problem. That's why we need to exam the small cases.
    The test example is a good inspiration. When consider n = 3, k = 2 with array [1, 3, 2], you may notice that it gives you 1, 2 these two distinct integers. If we want to have k distinct integers from 1, ..., k, what we can do?

    A nature way is to mimic the example. We put 1 in the first, then k + 1 in order to get k. The we put 2 to get k - 1, then k to get k - 2 and so on. For example, [1, k+1, 2, k, 3, k-1, ..., ]. The process will stop when we hit the integer k/2 + 1 for k = even and (k + 3) / 2 for k = odd. By doing so, we get the integers from 1 to k. Now, we need to take care of the next integer. Since we used up from 1 to k+1, then k+2 comes to the next. We can easily check that k+2 - (k/2 + 1) or (k+2) - (k+3)/2 are smaller or equal to k. Then we are done if we put k+2, k+3, ... n to the remaining of the array.

    class Solution {
    public:
        vector<int> constructArray(int n, int k) {
            //Put 1...k+1 in the first half of the array
            vector<int> array(n);
            int left = 1;
            int right = k + 1;
            int idx = 0;
            while (left <= right) {
                if (left < right) {
                    array[idx++] = left;
                    array[idx++] = right;
                } else {
                    array[idx++] = left;
                }
                left++;
                right--;
            }
            for (int i = idx; i < n; i++) {
                array[i] = k + i - idx + 2;
            }
            return array;
        }
    };
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.