C++ O(n)


  • 0

    Let's consider it

    n=5andk=4, then the vector could be [1, 5. 2, 4, 3]
    n=4andk=3, then the vector could be [1, 2, 5, 3, 4]

    So what happens if n=20 and k=4, we could construct [... 15,16,20,17,19,18],
    then the list [|a1 - a2|, |a2 - a3|, |a3 - a4|, ... , |an-1 - an|] is [1, 4, 3, 2, 1], the list has exactly 4 distinct integers.

    I think it should be an easy problem.

    class Solution {
    public:
        vector<int> constructArray(int n, int k) {
            vector<int> retVec(n);
            for(int i = 0; i < n - k; i++)
                retVec[i] = i + 1;
            
            bool isBig = false;
            retVec[n-k] = n;
            for(int i = n-k + 1; i < n; i++) {
                if(isBig) {
                    retVec[i] = retVec[i - 2] - 1;
                } else if(isBig == false) {
                    retVec[i] = retVec[i - 2] + 1;
                }
                isBig = ~isBig;
            }
            return retVec;
        }
    };
    

Log in to reply
 

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