首页 > 试题广场 >

奇怪的排序问题

[编程题]奇怪的排序问题

热度指数：1199 时间限制：C/C++ 5秒，其他语言10秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

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

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

示例1

输入

4,[4,1,2,3]

输出

备注:

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

算法知识视频讲解

JavaScript

紫荷雪

倒序遍历，当前数字比后面最小的数字大，则需要一次移动。

function wwork( n ,  a ) {
    // write code here
    let min = a[n-1];
    let num = 0;
    for(let i = n - 2; i >= 0; i--){
        let cur = a[i];
        if(a[i] > min){
            num++;
        } else {
            min = a[i];
        }
    }
    return num;
}

发表于 2021-01-18 21:07:03 回复(2)

JavaScript

IPzzzi

function wwork( n ,  a ) {
    // write code here
    if(n == 1){
        return 0;
    }
    var num = 0;
    var q = [];
    q.push(a[n-1]);
    for(var i = n-2; i >= 0; i--){
        if(a[i] > q[q.length-1]){
            num++;
            continue;
        }
        q.push(a[i]);
    }
    return num;
}

发表于 2021-05-17 11:53:06 回复(0)

Python 3

牛客844991771号

Python这运行速度就是比不上c 差太多了压根运行不完

s = 0
for i in range(0, n):
    m = max(a)
    if a[-1] != m:
        s += 1
    a.remove(m)
return s

发表于 2021-09-13 16:56:07 回复(0)

Rong姐姐好可爱

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 * 
 * @param n int整型 
 * @param a int整型一维数组 
 * @return int整型
 */
function wwork( n ,  a ) {
    // write code here
    // 从后往前遍历
    let count=0;
    if(n===0){
        return count;
    }
    let min=a[n-1];
    while(n>0){
        if(a[n-1]>min){
            count++;
        }else{
            min=a[n-1]
        }
        n--
    }
    
    return count;
}
module.exports = {
    wwork : wwork
};

发表于 2021-06-08 22:19:48 回复(0)

SaraNova

按照倒叙遍历的思路来，ac是ac了，但是我自己假设输入8,[3,5,6,7,8,1,2,4]

理论上应该是把后面几个往前放就升序了，只要3步，但是按照倒序遍历的思路来是5步，就很迷惑

发表于 2021-06-02 15:26:02 回复(1)

C/C++

VatalityWang

/**
     * 奇怪的排序问题
     * 操场上有n个人排成一队，这n个人身高互不相同，可将他们的身高视为一个1到n的排列。
     * 这时需要把队伍变成升序，也就是从矮到高排序。 
     * 每次可以选择一个人，让这个人和在他身后的人比高矮，如果比对方高，则交换位置并继续下一次比较，直到比对方矮或者已经在队尾。
     * 现在给出数n和一个1到n的排列，求最少的选择次数，使队伍变为升序。
     * **/
    int wwork(int n, vector<int>& a) {
        // write code here
        int i,count=0,order=n;
        for(i=n-1;i>=0;i--){
            if(a[i]>order)
                count++;
            order=min(a[i],order);
        }
        return count;
    }

发表于 2021-04-21 21:21:03 回复(0)