在列表中找到所有的山丘和山谷 [英] find all the hills and valley in a list

问题描述

我正在编写一个函数，以查找给定列表中的所有丘陵和山谷。例如，[1,0,0,0,1]返回3，[0,1,0,1,0]返回5。[0,2,2,1,1,0,0]返回3。一个数字（或具有相同值的连续数字）大于或小于两个邻居的数字，则被视为小山或山谷。

I am writing a function to find all the hills and valleys in a given list. For instance, [1,0,0,0,1] returns 3 and [0,1,0,1,0] returns 5. [0,2,2,1,1,0,0] returns 3. If a number (or consecutive numbers with same values) are bigger or smaller than both of its neighbors, it is considered as a hill or a valley.

下面是我的代码：

def hill_and_vally(s):
    if not s or len(s) < 2:
        return 0
    i = 0
    count = 0
    pre = None
    while i < len(s):
        if i == 0:
            while s[i] == s[i+1]:  # loop until value is different
                i += 1
            i += 1
            if i < len(s):       # check if it reaches the end 
                count += 1
                pre = s[i-1]     # track the previous value
        elif i == len(s) - 1:
            while s[i] == s[i-1]:  
                i -= 1
            i -= 1
            if i >= 0:
                count += 1
            break
        else:
            while s[i] == s[i+1]:
                i += 1
            i += 1
            if s[i] > s[i-1] and pre > s[i-1]:  # it is a valley
                count += 1
            elif s[i] < s[i-1] and pre < s[i-1]:  # it is a hill
                count += 1
            pre = s[i-1]
    return count

有人可以帮助我提高O（N）的复杂度吗？还是向我展示另一种更好的解决方案？请给我看一些例子。提前致谢。

Can someone help me to improve the complexity to O(N). Or show me another way to do it with better complexity? Please show me some examples. Thanks in advance.

推荐答案

这是我的处理方式：

• 计算连续元素之间的差异 d （从结果中删除 0 s）


• 计算符号在 d
中的变化次数

• 返回2并加上该计数（因为那里有一座小山，

• compute differences d between consecutive elements (remove 0s from result)
• count the number of times the sign changes in d
• return 2 plus that count (because there is a hill and a valley even in a monotonically increasing sequence)

在代码中：

def hill_and_vally(s):
    d=[x1-x0 for x0,x1 in zip(s,s[1:]) if x1!=x0]
    return 2+sum(d0*d1<0 for d0,d1 in zip(d,d[1:]))

当然可以用来实现循环和索引，但是 zip 和列表推导方式更Python化。

of course it can be implemented with for loops and indexes, but zip and list comprehensions is more pythonic.

zip（s，s [1：]）是获取对中相邻元素对的常用方法

zip(s,s[1:]) is a common way to get pairs of adjacent elements in a list.

测试：

>>> hill_and_vally([1,0,0,0,1])
3
>>> hill_and_vally([0,1,0,1,0])
5
>>> hill_and_vally([0,2,2,1,1,0,0])
3

处理诸如报告的 [1,1,1,1] 等极端情况作为练习：-）

Handling corner cases such as the reported [1,1,1,1] is left as an exercise :-)

这篇关于在列表中找到所有的山丘和山谷的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！