C++ code with comments


  • 0
    L
    class Solution {
    public:
        vector<int> constructArray(int n, int k) {
            //use 1 to n to construct k 
            
            //
            vector<int> ret;
            
            //in order to make k diff, we need 1 and k + 1
            
            //use 1 to 1 + k to make tail, tail only contribute diff 1, this will make sure in the future we will not add any different diff, so handle the tail first.
            
        
            for(int i = k + 2; i <= n; ++i)
            {
                ret.push_back(i);
            }
            
            //now every high - low couple make a new diff
            int low = 1;
            int high = 1 + k;
            
            while(low <= high)
            {
                if(low != high)
                {
                    ret.insert(ret.begin(), high);
                    ret.insert(ret.begin(), low);
                    --high;
                    ++low;
                }
                else
                {
                    ret.insert(ret.begin(), high);
                    ++low;
                    --high;
                }
            }
            
            
            return ret;
        }
    };
    

Log in to reply
 

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