详细信息:

  • 在给定数组numbers = {2, 7, 8, 5, 1, 6, 3, 9, 4}.判断以下条件的情况下,两个条件都应满足.

  • 如果为arr[i – 1] < arr[i] > arr[i + 1],其中1&lt;i&lt;N-1,则arr[i]是峰值元素.

  • 如果arr[0] > arr[1], then arr[0]是峰值元素,其中N是数组的大小.

  • 如果arr[N – 2] < arr[N – 1], then arr[N – 1]是峰值元素,其中N是数组的大小.

  • 如果数组中有more than one peak element个,则需要打印其中的minimum value个.


示例:

1st Iteration - 8, 6, 9 are peak values. 
Remove the smallest ele. Remove 6. 
New arr {2, 7, 8, 5, 1, 3, 9, 4}. Output Arr - {6}

2nd Iteration - 8, 9 are peak values. 
Remove the smallest ele. Remove 8. 
New arr {2, 7, 5, 1, 3, 9, 4}. Output Arr - {6, 8}

3rd Iteration - 7, 9 are peak values. 
Remove the smallest ele. Remove 7. 
New arr {2, 5, 1, 3, 9, 4}. Output Arr - {6, 7, 8}

4th Iteration - 5, 9 are peak values. 
Remove the smallest ele. Remove 5. 
New arr {2, 1, 3, 9, 4}. Output Arr - {6, 7, 8, 5}

5th Iteration - 2, 9 are peak values. 
Remove the smallest ele. Remove 2. 
New arr {1, 3, 9, 4}. Output Arr - {6, 7, 8, 5, 2}

6th Iteration - 9 are peak values. 
Remove the smallest ele. Remove 9. 
New arr {1, 3, 4}. Output Arr - {6, 7, 8, 5, 2, 9}

7th Iteration - 4 are peak values. 
Remove the smallest ele. Remove 4. 
New arr {1, 3}. Output Arr - {6, 7, 8, 5, 2, 9, 4}

8th Iteration - 3 are peak values. 
Remove the smallest ele. Remove 3. 
New arr {1}. Output Arr - {6, 7, 8, 5, 2, 9, 4, 3}

9th Iteration - 1 are peak values. 
Remove the smallest ele. Remove 1. 
New arr {1}. Output Arr - {6, 7, 8, 5, 2, 9, 4, 3, 1}

Output: {6, 8, 7, 5, 2, 9, 4, 3, 1}

我的代码:

nums = [2, 7, 8, 5, 1, 6, 3, 9, 4]

def deleteMinimalPeaks(nums):
    from queue import PriorityQueue as pq
    
    if len(nums) <= 1:
        return nums
    
    peakq = pq()
    out = []
    n = len(nums)
    
    ridx = [i+1 for i in range(n)]
    lidx = [i-1 for i in range(n)]
    
    nums.append(-1)
    
    if nums[0] > nums[1]:
        peakq.put((nums[0], 0))
        
    if nums[n-1] > nums[n-2]:
        peakq.put((nums[n-1], n-1))
        
    for i in range(1, n-1):
        if nums[i] > nums[i-1] and nums[i] > nums[i+1]:
            peakq.put((nums[i], i))
            
    if peakq.empty():
        nums.pop()
        return nums[::-1]
    
    while(not peakq.empty()):
        val, idx = peakq.get()
        out.append(val)
        
        if len(out) == len(nums):
            break
        
        if ridx[idx] <= n-1:
            lidx[ridx[idx]] = lidx[idx]
            
        if lidx[idx] >= 0:
            ridx[lidx[idx]] = ridx[idx]
            
        if ridx[idx] <= n-1 \
        and nums[ridx[idx]] > nums[ridx[ridx[idx]]] \
        and nums[ridx[idx]] > nums[lidx[ridx[idx]]]:
            peakq.put( (nums[ridx[idx]], ridx[idx]) )
            
        if lidx[idx] >= 0 \
        and nums[lidx[idx]] > nums[lidx[lidx[idx]]] \
        and nums[lidx[idx]] > nums[ridx[lidx[idx]]]:
            peakq.put( (nums[lidx[idx]], lidx[idx]) )
        
    return out

deleteMinimalPeaks(nums)

问题:

代码给出了正确的结果.

然而,有没有一种更有攻击性的方式来写innermost while loop?


推荐答案

我可能会使用IterTools来帮助导航结果.使用triplewise的配方并稍作修改,我们可以很容易地迭代列表中的多个值.

我们将进行的调整是在数据的开始和结束处添加缓冲区.这将允许我们检测我们是否处于数据的边缘.

from itertools import pairwise

def triplewise(iterable):
    for (a, _), (b, c) in pairwise(pairwise([None, *iterable, None])):
        yield a, b, c


nums = [2, 7, 8, 5, 1, 6, 3, 9, 4]
for a, b, c in triplewise(nums):
    print(a, b, c)
None 2 7
2 7 8
...
3 9 4
9 4 None

要创建一个只返回峰值的方法,您所要做的就是对照它的边缘判断中间数.我们知道None的值是边.

def find_peeks(iterable):
    for a, b, c in triplewise(iterable):
        if (a is None or b > a) and (c is None or b > c):
            yield b


nums = [2, 7, 8, 5, 1, 6, 3, 9, 4]
print(list(find_peeks(nums)))
[8, 6, 9]

要进行迭代,您可以让find_peeks方法也返回Peek的索引.然后,您可以使用MIN查找要删除的最小元素并继续:

def find_peeks(iterable):
    for i, (a, b, c) in enumerate(triplewise(iterable)):
        if (a is None or b > a) and (c is None or b > c):
            yield b, i


def iterative_peeks(iterable):
    while iterable:
        peek, index = min(find_peeks(iterable))
        yield peek
        del iterable[index]


nums = [2, 7, 8, 5, 1, 6, 3, 9, 4]
print(list(iterative_peeks(nums)))
[6, 8, 7, 5, 2, 9, 4, 3, 1]

Python相关问答推荐

基于Scipy插值法的三次样条系数

为什么我的sundaram筛这么低效

Beautifulsoup:遍历一个列表,从a到z,并解析数据,以便将其存储在pdf中.

Tensorflow tokenizer问题.num_words到底做了什么?

如何从比较函数生成ngroup?

如何将泛型类类型与函数返回类型结合使用?

如何在Airflow执行日期中保留日期并将时间转换为00:00

如何写一个polars birame到DuckDB

具有不同坐标的tkinter canvs.cocords()和canvs.moveto()

我可以同时更改多个图像吗?

如何导入与我试图从该目录之外运行的文件位于同一目录中的Python文件?

在FastAPI/Starlette中使用WebSockets时如何运行后台任务?

如何判断特定的OPC UA node 是否已经存在Asyncua?

Pandas 多重索引不返回级别和标签

用tab键改变焦点的Qt事件

如何验证像这样添加的对象属性:MyObj.newattribute=123

如何使用列表理解来计算高配对或低配对?

Django中带有ForeignKey的抽象模型无法按预期继承

SCRIT-学习定制转换器从底层模型抛出NotFittedError

我正在试着做一个简单的程序来判断学校的一个项目的调查数据,但它不起作用,有人能帮我吗?