不使用排序的最大三重积？

Question

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

问题：给定一个由n个整数组成的列表arr[0...（n-1）]。您必须计算一个列表输出[0...（n-1）]，以便对于每个索引i（在0和n-1之间，包括在内），输出[i]等于arr[0... i]中三个最大元素的乘积（如果i

示例：

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

我认为有一种更快、更有效的方法可以做到这一点。这是一个类似于@Q2Learn的思维过程，使用Python；更快：

def findMaxProduct(arr):
 
  #create a copy of arr
    
  solution = arr.copy()
  # make first 2 elements -1
  for i in range(0,2):
    solution[i] = -1
    
#for each item in copy starting from index 2, multiply  item from 2 indices b'4 (notice how each index of arr being multiplied is reduced by 2, 1 and then 0, to accommodate each move)
  
  for i in range(2, len(arr)):
    solution[i] = arr[i-2] * arr[i-1] * arr[i]
  return solution

check = findMaxProduct(arr)
print(check)

Answer 2

您可以创建一个包含三个当前最大整数的数组，并在通过原始数组时更新该数组。这就是为什么您总是有三个当前最大的数字，并且您将能够以O（n）的时间复杂性来解决这个问题。

Answer 3

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

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

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

• 复杂性：

三元素数组的排序和切片应该是O（1），因为每次atmost都有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;
}