我要招人

去企业版

首页 > 试题广场 >

小Q的排序

[编程题]小Q的排序

热度指数：4651 时间限制：C/C++ 2秒，其他语言4秒空间限制：C/C++ 128M，其他语言256M
算法知识视频讲解

小Q在学习许多排序算法之后灵机一动决定自己发明一种排序算法，小Q希望能将n个不同的数排序为升序。小Q发明的排序算法在每轮允许两种操作：

1、将当前序列中前n-1个数排为升序

2、将当前序列中后n-1个数排为升序

小Q可以任意次使用上述两种操作，小Q现在想考考你最少需要几次上述操作可以让序列变为升序。

输入描述:

输入包括两行，第一行包括一个正整数n(3≤n≤10^5)，表示数字的个数

第二行包括n个正整数a[i](1≤a[i]≤10^9)，即需要排序的数字，保证数字各不相同。

输出描述:

输出一个正整数，表示最少需要的操作次数

示例1

输入

6
4 3 1 6 2 5

输出

算法知识视频讲解

Python

牛客817844335号

#如果序列原本是有序的，就是0

#如果最后一个元素是最大值，只需要排序1次，直接输出1即可

#如果最后一个元素不是最大值，需要先排后n-1然后再排前n-1,直接输出2即可

#不用真的排序，判断情况直接输出0 1 2 就行

n = int(input())

a = list(map(int,input().split(' ')))
if a == sorted(a):
print(0)
elif a[-1] == max(a):
print(1)
else:
print(2)

发表于 2020-09-06 17:50:31 回复(0)

Python

燕过寒潭

n=int(input().strip())
a=input().strip().split()
for j in range(n):
    a[j]=int(a[j])
tmp=a.copy()
tmp.sort()
if a==tmp:
    print(0)
elif a[0]==tmp[-1] and a[-1]==tmp[0]:
    print(3)
elif a[0]==tmp[-1]&nbs***bsp;a[-1]==tmp[0]:
    print(2)
elif a[0]==tmp[0]&nbs***bsp;a[-1]==tmp[-1]:
    print(1)
else:
    print(2)

发表于 2020-08-21 12:33:58 回复(0)

Python

球球给我一个_Offer_吧

# 题目比较简单，在纸上画一画就能懂
def my_method(param) -> int:
    times = 0
    sort_param = sorted(param)
    if sort_param == param:
        return 0
    max_num, min_num = max(param), min(param)
    length = len(param)
    if param[length - 1] == min_num and param[0] == max_num:
        times += 3
    if param[length - 1] != max_num:
        times += 1
    if param[0] != min_num:
        times += 1
    return times

if __name__ == "__main__":
    counts = int(input())
    tool_list = input().split()
    print(my_method(tool_list))

发表于 2020-07-08 22:07:17 回复(0)

Python

wangkss_01

虽然问题不难，但是逻辑还是要一步一步屡清楚。

1.当初始输入已经是升序时，如1 2 3 4 5 6，此时不需要进行排序，输出为0；

2.当初始输入不是升序时：以4 3 6 2 1 5为例

1>首先前N-1个数进行升序排序，执行完这次动作之后，得到的是一个已经按升序排列并且长度为N-1的数组加上原数组的最后一个数，即1 2 3 4 6 5

然后需要判断是否有必要进行后N-1个数的排序动作。

a.假如最后一个数大于前N-1个数中的任意一个（或者说前N-1个数排序后的最后一个数），那么就无须再进行后N-1个数进行排序，输出1

b.假如最后一个数比较小，那么就有必要进行后N-1个数排序动作，这个动作执行完之后会有两种情况：

一、当最后一个数大于前N-1个数中的最小的数时，那么经过b的排序之后，升序完成，输出2

二、当最后一个数比前N-1个数中的最小的数还小时，那么经过b之后，它就变成一个数（第二小）加上一个已经是升序的数组，很明显，还需要对前N-1个数执行一次排序动作，即输出3

代码比较水，就不列了。

换成数学的逻辑语言描述如下(表述能力有限，谅解)：

输入长度为i的数列

发表于 2020-06-13 21:39:40 回复(0)

Python

lx的流星

while True:
    try:
        n=int(input().strip())
        inp=list(map(int,input().strip().split(' ')))
        #print(inp)
        if inp[0]==1 or inp[n-1]==n:
            print(1)
        else:
            print(2)
    except:
        break

发表于 2019-07-25 10:08:42 回复(0)