不使用排序的最大三重产品？

Question

我实现了最大的三重产品算法，但我使用了排序，这使我的时间复杂度为 O(nlogn)。有没有办法在没有临时排序数组的情况下实现它？

问题：给定一个包含 n 个整数 arr[0..(n-1)] 的列表。您必须计算一个列表 output[0..(n-1)] ，使得对于每个索引 i（在 0 和 n-1 之间，包括端点），output[i] 等于三个最大元素的乘积arr[0..i]（如果 i < 2，则等于 -1，因为 arr[0..i] 然后包含少于三个元素）。请注意，用于形成任何乘积的三个最大元素可能彼此具有相同的值，但它们在 arr 中必须位于不同的索引处。

例子：

var arr_2 = [2, 4, 7, 1, 5, 3];
var expected_2 = [-1, -1, 56, 56, 140, 140];

我的解决方案：

function findMaxProduct(arr) {
  // Write your code here
  if(!arr || arr.length === 0)  return [];
  
  let helper = arr.slice();
  helper.sort((a,b)=>a-b);   // THIS IS THE SORT
  
  let ans = [];
  let prod = 1;
  for(let i=0; i<arr.length; i++) {
    if(i < 2) {
      prod *= arr[i];
      ans.push(-1);
    }
    else {
      if(i === 3) {
        prod *= arr[i];
        ans.push(prod);
      } else if(arr[i] < helper[0]) {
        ans.push(prod);
      } else {
        const min = helper.shift();
        prod /= min;
        prod *= arr[i];
        ans.push(prod);
      }
    }
  }
  
  return ans;
}

谢谢

Answer 1

您不需要对其进行排序。您只需在每个索引处维护一个包含最大三个元素的数组。

对于前三个元素，很简单，您只需将它们的乘积分配给结果中的第三个元素。

对于接下来的元素，您将当前元素添加到三个最大元素数组中并对其进行排序，然后从 1 到 3（最大的三个）中取出元素，并分配结果数组中该索引处的元素的乘积。然后用最大的三个更新三元素数组。

• 复杂性：

这种三元素数组的排序和切片应该是 O(1)，因为每次数组中最多有 4 个元素。

总体复杂度为 O(n)。

你可以这样做：

function findMaxProduct(arr) {
  if(!arr)  return [];
  if (arr.length < 3) return arr.slice().fill(-1)
  let t = arr.slice(0,3)
  let ans = arr.slice().fill(-1,0,2) //fill first two with -1
  ans[2] = t[0]*t[1]*t[2];
  for(let i=3; i<arr.length; i++) {
    t.push(arr[i]);
    t = t.sort().slice(1,4);
    ans[i] = t[0]*t[1]*t[2];
  }
  return ans;
}