20190116-将特定数字插入一个已经排序好的序列并…

2019-01-21 02:42:32来源:博客园 阅读 ()

新老客户大回馈,云服务器低至5折

1. 有一个已经排好序的列表。现输入一个数,要求按原来的规律将它插入列表中

分析:已经排好序的列表也可能是升序也可能是降序,需要先确定列表的排序方式以升序为例,需要考虑4主要种情况:

Case1:小于列表的第一个值,则插入第一个

如s=[2,3,4],插入1,则结果应该为[1,2,3,4],1插入的位置应该为第0个

Case2:处于区间

如s=[2,4,5]插入3,则结果应为[2,3,4,5],2插入的位置应该为2和3之间,index为s[0]和s[1]之间

Case3:大于列表的最后一个值

如s=[2,4,5]插入6,则结果应为[2,4,5,6],6插入的位置应该为最末尾,index为s[len(s)]

Case4:列表中有重复值且与插入值一样的情况

如s=[2,4,4,5]插入4,则结果应为[2,4,4,4,5],4插入的位置应该为两个4之间,所以在Case2的基础上需要在前面3个case的基础上考虑相等的情况

def insert_num_in_order(s,num):
    result=[]
    if s[0]<s[-1]:
        #如果是升序,此处最好不要用s[0]与s[1]比较,因为可能有相等的情况,因此使用首尾进行比较
        for i in range(len(s)):
            if i ==0 and num<s[i]:
                #对应Case1的场景
                result.append(num)
                result.append(s[i])
            elif len(s)-1>i and num>=s[i] and num <s[i+1]:
                #此处需要写作开区间,否则会在特定情况执行两次,如2,3,3的序列中插入3,如果写作num>=s[i] and num <=s[i+1]的情况,则该条件会执行两次
                #对应Case2,Case4的场景,i处于0到len(s)-1之间,如果i=len(s)的情况则s[i+1]会超出range
          #此处还需考虑一个情况是[0,0,0,1,2]插入0的情况,因此elif条件中不能写成len(s)-1>i>0而是应该写成len(s)-1>i
result.append(s[i]) result.append(num) elif i ==len(s)-1 and num>=s[i]: #此处对应case3,case4的场景 result.append(s[i]) result.append(num) else: #其他场景 result.append(s[i]) #print('result',result) else: #如果是降序 for i in range(len(s)): if i==0 and num>s[i]: result.append(num) result.append(s[i]) elif len(s)-1>i and num<=s[i] and num >s[i+1]: result.append(s[i]) result.append(num) elif i ==len(s)-1 and num<=s[i]: result.append(s[i]) result.append(num) else: result.append(s[i]) return result

需要特别注意的一点:因为要考虑序列中有2个以上相同的值,并且和插入的值相同的情况,以降序为例所以写条件的的时候len(s)-1>i and num<=s[i] and num >s[i+1]这3个条件缺一不可,否则会有多次执行的情况

#升序执行检查
s = [0,0,1,2,3,4,5,6,7,8,9,10,10]
print(s)
print(insert_num_in_order(s,9))
#执行结果
#[0, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 9, 10, 10]
print(insert_num_in_order(s,0))
#执行结果
#[0, 0, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 10]
print(insert_num_in_order(s,10))
#执行结果
#[0, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 10, 10]
#降序执行检查
s1 = [10,10,9,8,7,6,5,4,3,2,1,1]
print(s1)
print(insert_num_in_order(s1,9))
#执行结果
#[10, 10, 9, 9, 8, 7, 6, 5, 4, 3, 2, 1, 1]
print(insert_num_in_order(s1,1))
#执行结果
#[10, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 1, 1]
print(insert_num_in_order(s1,10))
#执行结果
#[10, 10, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 1]

 


原文链接:https://www.cnblogs.com/hyj691001/p/10279457.html
如有疑问请与原作者联系

标签:

版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有

上一篇:python 购物车小程序(列表、循环、条件语句)

下一篇:【Python3爬虫】使用异步协程编写爬虫