时间戳

首页 > 解决方案 > 计数连续锯齿子阵列

python - 计数连续锯齿子阵列

问题描述

给定一个整数数组 arr，你的任务是计算代表至少两个元素的锯齿序列的连续子数组的数量。

对于 arr = [9, 8, 7, 6, 5]，输出应该是 countSawSubarrays(arr) = 4。由于所有元素都按降序排列，因此不可能形成任何长度为 3 的锯齿子数组或者更多。有 4 个可能的子数组包含两个元素，所以答案是 4。

对于 arr = [10, 10, 10]，输出应该是 countSawSubarrays(arr) = 0。由于所有元素都相等，所以没有一个子数组可以是锯齿的，所以答案是 0。

对于 arr = [1, 2, 1, 2, 1]，输出应为 countSawSubarrays(arr) = 10。

所有包含至少两个元素的连续子数组都满足问题的条件。有 10 个可能包含至少两个元素的连续子数组，所以答案是 10。

解决这个问题的最佳方法是什么？我在这里看到了一个可能的解决方案：https ://medium.com/swlh/sawtooth-sequence-java-solution-460bd92c064

但是这个代码在 [1,2,1,3,4,-2] 的情况下失败了，答案应该是 9 但它是 12。

我什至尝试过蛮力方法，但我无法绕开它。任何帮助，将不胜感激！

编辑： 感谢 Vishal 的响应，经过一些调整，这里是 python 中的更新解决方案。时间复杂度：O(n) 空间复杂度：O(1)

def samesign(a,b):
    if a/abs(a) == b/abs(b):
        return True
    else:
        return False

def countSawSubarrays(arr):
    n = len(arr)
    
    if n<2:
        return 0

    s = 0
    e = 1
    count = 0
    
    while(e<n):
        sign = arr[e] - arr[s]
        while(e<n and arr[e] != arr[e-1] and samesign(arr[e] - arr[e-1], sign)):
            sign = -1*sign
            e+=1
        size = e-s
        if (size==1):
            e+=1
        count += (size*(size-1))//2
        s = e-1
        e = s+1
    return count

arr1 = [9,8,7,6,5]
print(countSawSubarrays(arr1))
arr2 = [1,2,1,3,4,-2]
print(countSawSubarrays(arr2))
arr3 = [1,2,1,2,1]
print(countSawSubarrays(arr3))
arr4 = [10,10,10]
print(countSawSubarrays(arr4))

结果：4 9 10 0

标签： pythonarraysalgorithmdynamic-programming

解决方案

这可以通过将数组拆分为多个锯齿序列来解决……这是 O(n) 操作。例如 [1,2,1,3,4,-2] 可以分成两个序列 [1,2,1,3] 和 [3,4,-2] 现在我们只需要做 C(size ,2) 两个部分的操作。

这是解释这个想法的psedo代码（没有处理所有极端情况）

 public int countSeq(int[] arr) {
int len = arr.length;
if (len < 2) {
  return 0;
}

int s = 0;
int e = 1;
int sign = arr[e] - arr[s];
int count = 0;

while (e < len) {
  while (e < len && arr[e] - arr[e-1] != 0 && isSameSign(arr[e] - arr[e-1], sign)) {
    sign = -1 * sign;
    e++;
  }
  // the biggest continue subsequence starting from s ends at e-1;
  int size = e - s;
  count = count + (size * (size - 1)/2); // basically doing C(size,2)
  s = e - 1;
  e = s + 1;
}

return count;

}

推荐阅读