My java O(n) greedy solution


  • 0
    L

    The k distinct differences can be conveniently chosen to be 1, 2, 3 ... k. To make sure the biggest difference "k" exists, we may start from the smallest number 1, and then take 1 + k in the second position next to it. The second largest difference k - 1 can be obtained by setting the third number as k + 1 - (k - 1). We can similarly select the rest numbers following this small-big-small pattern: array[i] = array[i - 1] + / - (k - i + 1). For numbers that have not been used (from k + 2 to n), we just leave them in increasing order which won't produce new distinct differences.

    class Solution {
        public int[] constructArray(int n, int k) {
            int[] array = new int[n];
            array[0] = 1;
            for (int i = 1; i <= k; i++) {
                if ((i & 1) != 0)
                    array[i] = array[i - 1] + k - i + 1;
                else
                    array[i] = array[i - 1] - k + i - 1;
            }
            for (int i = k + 1; i < n; i++)
                array[i] = i + 1;
            return array;
        }
    }
    

Log in to reply
 

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