首页 > 试题广场 >

排序次数

[编程题]排序次数
  • 热度指数：2239 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 64M，其他语言128M
  • 算法知识视频讲解
\hspace{15pt}给定一个长度为 n 的整数数组 \{a_1,a_2,\dots,a_n\}。小摩希望将数组调整为单调不减的顺序，即满足 a_1 \leqq a_2 \leqq\dots \leqq a_n。
\hspace{15pt}他只能重复进行以下操作：
{\hspace{20pt}}_\texttt{1.}\,任选一个下标 i\,\left(1\leqq i\leqq n\right)；
{\hspace{20pt}}_\texttt{2.}\,将元素 a_i 从当前位置删除，并插入到数组的末尾（其余元素的相对顺序保持不变）。
\hspace{15pt}请你求出使数组变为严格递增所需的最少操作次数。

输入描述:
\hspace{15pt}第一行输入一个整数 n\left(1\leqq n\leqq 5\times 10^3\right) 表示数组的长度。 
\hspace{15pt}第二行输入 n 个整数 a_1,a_2,\dots,a_n\left(-10^3\leqq a_i\leqq 10^3\right) 表示数组元素。


输出描述:
\hspace{15pt}在一行上输出一个整数，代表最少操作次数。
示例1

输入

4
19 7 8 25

输出

2

说明

\hspace{15pt}对于第一组样例： 
\hspace{23pt}\bullet\,第一次操作，将 19 移动到末尾，数组变为 \{7,8,25,19\}； 
\hspace{23pt}\bullet\,第二次操作，将 25 移动到末尾，数组变为 \{7,8,19,25\}，此时数组严格递增。 
\hspace{15pt}因此答案为 2。
算法知识视频讲解
添加回答
ABCNB头像 ABCNB 
# 解题思路：
# 首先将a排序，变为b
# 然后查看a中有多少是按照b中由小到大的顺序排列的
# 举例：a=[1,5,2,6,3,7,4] b=[1,2,3,4,5,6,7]
# 这时a中 1 2 3 4 为按照b中由小到大排序
# 若要将a变为b，只需依次移动5 6 7 到数列的末尾
num=int(input())
a=list(map(int,input().split()))
b=sorted(a)
j=0  count=0 for i in range(len(a)):  if a[i] == b[j]:
        j+=1    count+=1  print(len(b)-count)

发表于 2018-11-19 17:47:23 回复(0)
嘟嘟6668头像 嘟嘟6668 
import java.util.*;

public class Main {

    public static void main(String[] args) {
        Scanner scan=new Scanner(System.in);
        while(scan.hasNext()){
            int n=scan.nextInt();
            int[]data=new int[n];
            for(int i=0;i<n;i++)
                data[i]=scan.nextInt();
            System.out.println(get(data));
        }
    }
    public static int get(int[]data){
        int[] copy=new int[data.length];
        System.arraycopy(data,0,copy,0,data.length);
       Arrays.sort(copy);
       int n=data.length;
       int max=0;
       int i=0;
       int j=0;
       for(;i<n&&j<n;){
           if(data[i]!=copy[j]){
               i++;
           }else{
               i++;
               j++;
           }
       }
        return n-j;
    }
}

发表于 2019-04-16 18:56:08 回复(0)
Jae-hhu头像 Jae-hhu 
n=int(raw_input())
a=map(int,raw_input().strip().split(' '))
b=sorted(a)
num,j=0,0 for i in range(len(b)): if b[j]==a[i]:
        j,num=j+1,num+1  print len(b)-num
发表于 2018-07-26 15:09:32 回复(0)
Python
白色纯度头像 白色纯度
O(n)时间复杂度，找到最小的元素，遍历后面的元素即可！
本来就是解决排序的问题，你来个先排序再处理有点画蛇添足了。
不需要对原数组排序，只需要找到原数组最小的元素后面有多少个顺序元素的数量即可。
因为最小的元素后面的顺序元素不需要额外操作来排序，所以其余的元素都是要额外操作来排序的。 
def solve(num):
    x = num.index(min(num))
    stack = [num[x]]
    while x<len(num):
        if num[x]>=stack[-1]:
            stack.append(num[x])
        x += 1
    return len(num)-len(stack)+1
if __name__=='__main__':
    n = int(raw_input().strip())
    num = list(map(int,raw_input().split()))
    print(solve(num))


编辑于 2019-09-12 16:37:05 回复(0)
wylu头像 wylu 
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;

/**
 * @author wylu
 */
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        String[] strs = br.readLine().split(" ");
        int[] a = new int[n];
        int[] b = new int[n];
        for (int i = 0; i < n; i++) {
            a[i] = Integer.parseInt(strs[i]);
            b[i] = a[i];
        }

        Arrays.sort(b);
        int count = 0;
        for (int i = 0, j = 0; i < a.length; i++) {
            if (a[i] == b[j]) {
                count++;
                j++;
            }
        }
        System.out.println(a.length - count);
    }
}

发表于 2019-01-18 19:12:01 回复(0)
蝴蝶没了头像 蝴蝶没了 
n=input()
a=map(int,raw_input().split())
l=0
for i in range(n):
    if a[n-1] < a[i]:
        l += 1
print(l)

发表于 2018-08-07 16:47:32 回复(2)
Python3
又又又熬夜了头像 又又又熬夜了
n = int(input())
lst = [int(x) for x in input().split()]

while len(lst) > 0 and lst[0] == min(lst):
    lst = lst[1:]

if len(lst) == 0:
    print(0)
else:
    min_idx = len(lst) - lst[::-1].index(min(lst)) - 1
    second_min = min(lst[:min_idx])
    result = min_idx + sum([x > second_min for x in lst[min_idx + 1:]])
    print(result)
发表于 2024-08-17 18:49:57 回复(0)
Shelven丶头像 Shelven丶 
#include <bits/stdc++.h>
using namespace std;

int main()
{
	int z;
	cin >> z;
	vector<int> v1, v2;
	while (z--)
	{
		int x;
		cin >> x;
		v1.push_back(x);
		v2.push_back(x);
	}
	sort(v2.begin(), v2.end());
	int l1 = 0, l2 = 0, index = 0;
	while (l1 < v2.size())
	{
		if (v1[l1] == v2[l2])
		{
			l1++;
			l2++;
			index++;
		}
		else l1++;
	}
	cout << v1.size() - index;
}

发表于 2020-04-28 15:05:49 回复(0)
夏花爱秋叶头像 夏花爱秋叶
//思路:首先判断是否是arr[k,-1]的min?如果是，则k+1,如果不是，则arr.splice(k,1),arr.push(arr[k]),num+1;
var n=parseInt(readline());//数量
var arr=readline().split(' ').map(Number);//数字数组
var o_arr=arr.slice();//深拷贝
var sum=0;//改变次数
//排序(选择排序)
for(var i=0;i<n;i++){
    var i_min=arr[i];
    var index=null;
    for(var j=i+1;j<n;j++){
        if(arr[j]<i_min){
            i_min=arr[j];//记录当前最小值
            index=j;
        }
    }
    //交换数据
    if(index!=null){
        var tem=arr[index];
        arr[index]=arr[i];
        arr[i]=tem;
    }
}
for(var i=0;i<n-1;i++){
    // 如果最小值在次小值右边则改变,注意是lastIndexOf,因为存在同值数字
    if(arr[i]!=arr[i+1]&&o_arr.lastIndexOf(arr[i])>o_arr.indexOf(arr[i+1])){
        sum++;//次数加一
        o_arr.push(arr[i+1]);//添加
        o_arr.splice(o_arr.indexOf(arr[i+1]),1);//删除
    }
}
print(sum);
发表于 2020-01-14 23:24:35 回复(0)
我说所有的酒，都不如你头像 我说所有的酒，都不如你
import java.util.*;

public clas***ain{
    public static void main(String[] arg***r />         Scanner sc=new Scanner(System.in);
        int n=sc.nextInt();
        int []a=new int [n];
        for(int i=0;i<n;i++){
            a[i]=sc.nextInt();
        }
            int flag=0;
            int temp=0;
            for(int i=1;i<n;i++){
                if(a[i]<a[i-1]){
                    flag++;
                    temp=a[i];
                    a[i]=a[i-1];
                    a[i-1]=temp;
                }
            }
        System.out.println(flag);
    }
}
发表于 2019-05-21 10:23:51 回复(0)
赵俊锋头像 赵俊锋 
num=int(input())
a=list(map(int,input().split()))
b=sorted(a)
j=0
count=0
for i in range(len(b)):
    if b[j]==a[i]:
        j+=1
        count+=1
print(len(b)-count)

发表于 2018-09-20 15:59:45 回复(0)
乐观的摸摸头17头像 乐观的摸摸头17
import sys

n = int(sys.stdin.readline().strip())
a = list(map(int,sys.stdin.readline().strip().split()))
count = 0
for i in range(len(a)):
         if(a[i]> a[-1]):
             count += 1        
print(count)

发表于 2018-09-05 14:08:29 回复(0)
秒速__五厘米头像 秒速__五厘米

选择排序吗

发表于 2018-08-03 10:44:29 回复(0)
——佚名头像 ——佚名 

	#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int main(){
    int n;
    cin>>n;
    vector<pair<int,int>>arr;
    int k=0;
    while(n!=0){
        int curnum;
        cin>>curnum;
        arr.push_back(make_pair(curnum,k++));
        --n;
    }
    sort(arr.begin(),arr.end());
    int count=1;
    while(n+1<arr.size()&&arr[n+1].second>arr[n].second){
        count++;
        ++n;
    }
    cout<<arr.size()-count;
    return 0;
}
发表于 2018-07-24 14:03:38 回复(0)
WAK头像 WAK
#include<bits/stdc++.h>
using namespace std;
int main(){
    int n;
    while(cin>>n){
        vector<int> vec;
        for(int i = 0;i<n;i++){
            int x;
            cin>>x;
            vec.push_back(x);
        }
        vector<int> temp = vec;
        sort(temp.begin(),temp.end());
        int a = 0;
        int b = 0;
        int num = 0;
        while(a<vec.size()){
            if(vec[a]==temp[b]){
                a++;
                b++;
                num++;
            }
            else{
                a++;
            }
        }
        cout<<n-num<<endl;
    }
    return 0;
}
发表于 2018-07-18 17:28:11 回复(0)
提交观点

问题信息

C++工程师 iOS工程师 安卓工程师 数组 运维工程师 前端工程师 算法工程师 PHP工程师 排序 模拟 摩拜 数学 Java工程师
来自：摩拜2018校招算法工...
上传者：小小
难度：
15条回答 6070浏览

热门推荐

通过挑战的用户

查看代码

相关试题

排序次数

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号