Short Java forcing Timsort-adaptation


  • 0

    If I'm not mistaken, Arrays.sort(Integer[]) (not Arrays.sort(int[])) will recognize and merge the two runs in O(n). Given that it's an adaptation of Timsort and the documentation also says "[It] can take advantage of ascending and descending order in different parts of the the same input array. It is well-suited to merging two or more sorted arrays: simply concatenate the arrays and sort the resulting array."

    public int[] sortTransformedArray(int[] nums, int a, int b, int c) {
        Integer[] transformed = Arrays.stream(nums)
                                      .map(x -> a*x*x + b*x + c)
                                      .boxed().toArray(Integer[]::new);
        Arrays.sort(transformed);
        return Arrays.stream(transformed).mapToInt(i -> i).toArray();
    }

Log in to reply
 

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