基于输入的算法无法用于排序平方数组的算法

Question

我正在努力构建一种算法，该算法为一系列非核心整数制成，这并没有通过我的某些测试。我想知道为什么？我还包括了一个样本输入和输出。

import java.util.*;

class Program {

  public int[] sortedSquaredArray(int[] array) {
        int[] res = new int[array.length];
        int leftPointer = 0; 
        int rightPointer = array.length - 1;
        int counter = 0; 
        while (counter < array.length) {
            int leftSquared = array[leftPointer] * array[leftPointer];
            int rightSquared = array[rightPointer] * array[rightPointer]; 
            if (leftSquared < rightSquared) {
                res[counter] = leftSquared;
                leftPointer++;
            } else if (rightSquared <= leftSquared) {
                res[counter] = rightSquared; 
                rightPointer--;
            }
            counter++;
        }
        return res;
  }
}

"array": [-50, -13, -2, -1, 0, 0, 1, 1, 2, 3, 19, 20]

预期输出：

[0, 0, 1, 1, 1, 4, 4, 9, 169, 361, 400, 2500]

我得到的：

[400, 361, 9, 4, 1, 1, 0, 0, 1, 4, 169, 2500]

Answer 1

正如@greybeard写道的那样：您的错误是从下端填充，但是您还不知道最低的正方形，因为您正在检查具有最大平方值的两个数字。

此功能应执行您想要的操作：

    public int[] sortedSquaredArray(int[] array)
    {
        if (array.length == 0 || array[0] >= 0)
            return array;
            
        int[] res = new int[array.length];
        int leftPointer = 0; 
        int leftSquared = array[leftPointer] * array[leftPointer];
        int rightPointer = array.length - 1;
        int rightSquared = array[rightPointer] * array[rightPointer]; 
        int counter = rightPointer; 
        while (counter >= 0)
        {
            if (leftSquared >= rightSquared)
            {
                res[counter] = leftSquared;
                leftPointer++;
                leftSquared = array[leftPointer] * array[leftPointer];
            }
            else
            {
                res[counter] = rightSquared; 
                rightPointer--;
                rightSquared = array[rightPointer] * array[rightPointer];
            }
            counter--;
        }
        return res;
    }

注意第3和4行中的优化，并仅在需要时计算平方值。另外，此功能不是在实地排序！它正在返回一个带有排序正方形的新数组。可以通过在返回或直接使用传递的数组之前将值从排序的数组重新分配到传递数组的值来实现现场排序指针指向更大的价值。

您可以使用示例数据在这里。

Answer 2

如果 将数组指定为越来越多的顺序，那么您的尝试非常接近：
只需填充较大的正方形到较低的结果即可。
（如果数组以非阴性值开头，则只需返回输入数组的（副本）即可。）