奇怪的排序问题

NC211735. 奇怪的排序问题

描述

操场上有 n个人排成一队，这 n 个人身高互不相同，可将他们的身高视为一个 1 到 n 的排列。
这时需要把队伍变成升序，也就是从矮到高排序。
每次可以选择一个人，让这个人和在他身后的人比高矮，如果比对方高，则交换位置并继续下一次比较，直到比对方矮或者已经在队尾。

现在给出数 n 和一个 1 到 n 的排列，求最少的选择次数，使数组变为升序。

输入描述

n<=10^6
数据包含一个整数n和一个含有n个元素的数组，表示从队头到队尾的人的身高。
输出一个整数表示答案。

示例1

输入:

4,[4,1,2,3]

输出:

原站题解

上次编辑到这里，代码来自缓存点击恢复默认模板

C++(clang++11) 解法, 执行用时: 339ms, 内存消耗: 29648K, 提交时间: 2020-12-18 20:41:53

class Solution {
public:

    int wwork(int n, vector<int>& a) {
		int mi=n;
		int ans=0;
		for(int i=n-1;i>=0;i--) {
			if(a[i]>mi)ans++;
			mi=min(a[i],mi);
		}
		return ans; 
	}
};

Python3(3.9) 解法, 执行用时: 9067ms, 内存消耗: 134972K, 提交时间: 2020-12-18 21:54:10

class Solution:
    def wwork(self , n , a ):
        m=n+1
        ans=0
        for i in a[n::-1]:
            if i<m:m=i
            else:ans+=1
        return ans

上一题

下一题

详情