查找阵列分区最大（左）<最小（右） - 可能在O（N）时间？

我刚刚尝试了一个编码挑战来编写一个函数，该函数返回数组数组中所有可能的最短左分区的长度，其所有元素都小于相应右分区中的所有元素。查找阵列分区最大（左）<最小（右） - 可能在O（N）时间？

考虑到每月温度读数可变，冬季温度低于所有夏季温度的规则，给出的情景是找到“冬季”和“夏季”之间的差距。我们可以假设至少有一个正确的分区，目标是获得最短的冬季。

是否可以在O（N）时间内完成此操作，即处理时间随温度读数的数量线性增加？最快的解决方案，我可以拿出必须找到每一个最大的冬季温度被认为是最低的夏季温度（最低数量在正确的分区）：

function shortestWinterLength temps 
    maxWinterTemp = -Infinity 

    for i from 0 til temps.length 
     minSummerTemp = Infinity 

     for j from i + 1 til temps.length 
      minSummerTemp = Math.min minSummerTemp, temps[j] 

     maxWinterTemp = Math.max maxWinterTemp, temps[i] 

     if maxWinterTemp < minSummerTemp 
      return i + 1

来源

2017-10-11 Gus Hogg-Blake

在问题中提到的方法计算分（临时工[我+1]，... temps [n]）效率低下，因为许多类似的比较是针对不同的i值进行的。

取而代之，所有“最小”值可以通过执行一次通过阵列来获得，但是通过从右向左重复。

因此，有必要执行从右到左的初始传递，这会将迄今为止所达到的最小值存储在辅助数组中。之后，您可以使用与当前解决方案中的i相同的循环，但j上的内循环将被替换，只需从刚刚计算的辅助数组中检索“min”即可。

该解决方案具有O（n）复杂性。

来源

2017-10-11 13:51:37 qwertyman

是的，O(n)解决方案是可能的，但有额外的内存。

让我们来填充阵列minR其中minR[i] = min(A[i], ..., A[n])。

该数组的值可以在O(n)中计算。我们只是通过以相反的顺序初始阵列进行迭代，并计算最后一个数组元素中的最小值：

minR[n-1] = a[n-1] 
for i from n-2 downto 0 
    minR[i] = min(minR[i+1], A[i])

然后，所有你需要的是通过数组进行迭代计算第一i数组元素的最大值和比较该值与minR[i+1]：

maxL = 0 
for i from 0 to n-2 
    maxL = max(maxL, A[i]) 
    if maxL < minR[i+1] then 
     outputResult(i)

来源

2017-10-11 13:53:00 DAle

代码：

def shortestWinterLength(listofTemperatures): 

    if len(listofTemperatures) == 0 : 
     return 0 

    length = len(listofTemperatures) 
    winter_high = listofTemperatures[0] 
    overall_high = listofTemperatures[0] 
    winter_length = 0 

    # Get max in the left array 
    for temperature in listofTemperatures: 
     if temperature <= winter_high : 
      winter_high = overall_high 
     elif temperature > overall_high : 
      overall_high = temperature 

    # count all the values which are less than max in left array 
    for temperature in listofTemperatures : 
     if temperature <= winter_high : 
      winter_length += 1 

    # total length of the left array 
    return winter_length

时间复杂度 - O（N）
空间复杂度 - O（1）

来源

2018-01-03 21:45:16

查找阵列分区最大（左）<最小（右） - 可能在O（N）时间？

回答

相关问题