(Google)谷歌笔试算法题:要求相邻的两个数都不小于或者不大于其本身的排序

如题,要求相邻的两个数都不小于或者不大于其本身的排序, 那么也就是说每个数字必须同时大于等于或者小于等于它左右两边的数字,例如   3>=2<=6,那么这里2就是同时同于等于3且小于等于6,那么如果多来点数据就是    3>=2<=6>=5<=10>=2<=6

题目描述可能本身比较模糊,我们举例来看:

一组数据,比如已经排序好了(排序好的数据看着比较方便)

1,2,3,4,5,6,7

我们现在需要变成每个数字都大于等于或者小于等于它相邻的两个数

1 <= 3 >= 2 <= 5> =4 < =7 >= 6        

现在排序的方法有很多,我们可以先求出中位数,然后开始补,也可以先排序,然后倒数第二和倒数第一换位等等,但是这些都是需要先排序,而这里我们用一种一次排好的方法,即O(n),

上图:

看清楚了吗?我们这里一次排序,直接写入列表,因为所有数字他不是 不小于 就是 不大于

先把1 写入,

然后写入2,

然后写入3,这时候不满足条件了交换2和3的位置

然后写入4,

然后写入5,交换

写入6........

这里因为我用的是已经排好序的例子,其实大家可以想一下,乱序的也无所谓,只要满足条件,直接排序,没有影响

上代码:

#!D:/workplace/python
# -*- coding: utf-8 -*-
# @File  : 大小大小排序.py
# @Author: WangYe
# @Date  : 2019/5/21
# @Software: PyCharm

in_data = input()
data = in_data.split(',')
out = []   #输出列表

def compare(num1,num2):  #比较函数
    if num1 > num2:
        return 0
    if num1 < num2:
        return 1
    if num1 == num2:
        return 2

for k in range(len(data)):

    if (k - 1) < 0:  #存入首位
        out.append(int(data[0]))
    else:
        num1 = int(data[k-1])
        num2 = int(data[k])

        if (k%2) == 0:                    #区分基数还是偶数,也其实就是为了相邻的符号判断不同而已
            if compare(num1,num2) == 1:
                out.append(num2)
                out[k-1],out[k] = out[k],out[k-1]   #元素交换
            else:
                out.append(num2)
        else:
            if compare(num1, num2) == 0:
                out.append(num2)

                out[k - 1], out[k] = out[k], out[k - 1]  # 元素交换
            else:
                out.append(num2)

print(out)

截图:

或者乱序的

再来几个或者等于号的

ok,大功告成

版权声明:本文为qq_28626909原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/qq_28626909/article/details/90415286