Java, Two pointers method with explanation, very easy to understand


  • 0
    C

    We can tell that the final array will look like this:

    1, 1 + k, 1 + 1, 1 + k - 1, 1 + 2 ... k + 2, k + 3.. n
    0     1        2           3           4
    

    We can easily tell that when index i % 2 == 0, res[i] = (right--), otherwise, res[i] = (left ++)
    , so we come out with the solution :)

    public int[] constructArray(int n, int k) {
            
            int[] res = new int[n];
            // the maximum different gaps are n - 1
            if (k == 0 || k > n - 1) return res;
            
            int left = 1;
            int right = k + 1;
    
            int index = 0;
            while (left <= right) {
                if (index % 2 != 0) res[index ++] = right --;
                // index % 2 == 0
                else res[index ++] = left ++;
            }
            
            int count = n - res[1];
            // *** be careful about the conditions here
            while (count > 0) {
                res[index ++] = n - (count - 1);
                count --;
            }
            return res;
        }
    

Log in to reply
 

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