C++, concise code, O(n)


  • 10
    Z

    The requirement of k distinct distance can be achieved from 1, 2, ..., k+1 (<= n), by the following strategy:

    1, k+1, 2, k, 3, k-1 ...;
    The distance of this sequence is k, k-1, k-2, ..., 2, 1
    

    Then append the remaining numbers to the list.

    class Solution {
    public:
        vector<int> constructArray(int n, int k) {
            int l = 1, r = k+1;
            vector<int> ans;
            while (l <= r) {
                ans.push_back(l++);
                if (l <= r) ans.push_back(r--);
            }
            for (int i = k+2; i <= n; i++)
                ans.push_back(i);
            return ans;
        }
    };
    

  • 1

    Java version based on the same idea:

    class Solution {
        public int[] constructArray(int n, int k) {
            int[] res = new int[n];
            int l = 1, r = k + 1, i = 0;
            while (l <= r) {
                res[i++] = l++;
                if (l <= r)
                    res[i++] = r--;
            }
            for (int j = 0; j + i < n; j++) {
                res[j + i] = k + 2 + j; 
            }
            return res;
        }
    }
    

    Also, I think a certain point need to be clarified. In the case of (n,k) = (5,3), we first arrange 1..4 and then append 5, we have 1 4 2 3 + 5. It is for sure that there will be 3 diffs in 1 4 2 3, but it remains to be proved that 3 5 won't introduce an additional distinct diff (everything after 5, if any, need not to be worried, since they all form diff of 1, and is surely covered by the k diffs of 1..k+1).
    The proof of this is actually pretty trivial, since 5, which is k+2 can only introduce a new diff with the trailing number of whatever the result that is formed from 1..k+1, this trailing diff can only be within the range of 1..k+1. Don't panic for now, k+1 is actually untenable: to produce diff of k+1, we have to make sure that the subarray formed from 1..k+1 ends with 1, and this will never be the case: even when k is smallest as 1, the trailing number will be 2, and the maximum of the newly introduced trailing diff can only be k. Thus the trailing diff is in the range of 1..k, and there is nothing new that has not already been covered by the subarray formed from 1..k+1. In total, the entire array still contributes only k distinct diffs.


Log in to reply
 

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