快速排序问题-无法获得正确的结果

Question

我正在研究HackerRank的Quicksort2问题。我无法弄清楚它如何让我输出解决方案。

我尝试在创建排序数组时进行console.log，将排序数组的数组和转换为字符串的数组的数组。从processData函数返回似乎无效。

function checkSort(arr) {
    for (let i = 0; i < arr.length - 1; i++) {
        if (arr[i] > arr[i + 1]) return false;
    }
    return true;
}

function processData(input) {
    let sortedArrays = [];
    quickSort(input);

    function quickSort(input) {

        if (input.length <= 1) return input;

        let pivot = [input[0]];
        let left = [], right = [];
        for (let i = 1; i < input.length; i++) {
            input[i] < pivot ? left.push(input[i]) : right.push(input[i]);
        }

        let newArr = quickSort(left).concat(pivot, quickSort(right));
        if (checkSort(newArr)) sortedArrays.push(newArr);
        return newArr;
    }
    console.log(sortedArrays);
}

我期望它与HackerRank的期望输出匹配。

Answer 1

您的实现过程中有几个问题：

下面是任务描述中的引号：

在此挑战中，每当您的分区方法完成时，即每当两个子数组与数据透视表合并在一起时，就打印您的数组。

但是，您尝试在问题出现时为每个步骤打印排序后的数组，而不是子数组。因此，在返回子数组之前（在您的情况下为newArr），请先打印该子数组。不要忘记使用join格式化输出。

另一个引号：

将有两行输入：

数组的大小

数组的n个数字

您的processData期望已解析的输入，也就是可以使用的数组。如果它接收到原始输入（两行数据），则应相应地对其进行解析。例如，可以将它们解析如下：

...
function processData(input) {
    var lines = input.split('\n')
    var len = lines[0]
    var arr = lines[1].split(' '); 
...

因此您的固定代码如下：

function processData(input) {
    var lines = input.split('\n')
    var len = lines[0]
    var arr = lines[1].split(' ');
    quickSort(arr);
        function quickSort(input) {

        if (input.length <= 1) return input;

        let pivot = [input[0]];
        let left = [], right = [];
        for (let i = 1; i < input.length; i++) {
            input[i] < pivot ? left.push(input[i]) : right.push(input[i]);
        }

        let newArr = quickSort(left).concat(pivot, quickSort(right));
        // print the subarray once the partitioning for this step has finished
        console.log(newArr.join(' '))
        return newArr;
    }
}