首页 > 试题广场 >

排序

[编程题]排序

热度指数：9197 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

牛牛有一个长度为n的整数序列,牛牛想对这个序列进行重排为一个非严格升序序列。牛牛比较懒惰,他想移动尽量少的数就完成重排,请你帮他计算一下他最少需要移动多少个序列中的元素。(当一个元素不在它原来所在的位置,这个元素就是被移动了的)

输入描述:

输入包括两行,第一行一个整数n(1 ≤ n ≤ 50),即序列的长度
第二行n个整数x[i](1 ≤ x[i] ≤ 100),即序列中的每个数

输出描述:

输出一个整数,即最少需要移动的元素个数

示例1

输入

3
3 2 1

输出

算法知识视频讲解

Java

成程晨

import java.util.*;
public class Main{
public static void main(String[] args){
try(Scanner in = new Scanner(System.in)){
int n = in.nextInt(),i = 0;
int[] a = new int[n];
while(i < n){
a[i++] = in.nextInt();
}
System.out.println(helper(a));
}
}
public static int helper(int[] a){
int[] b = new int[a.length];
System.arraycopy(a,0,b,0,a.length);
Arrays.sort(b);
int count = 0;
for(int i = 0;i < a.length;i++){
if(a[i] != b[i]) count++;
}
return count;
}
}

发表于 2019-01-15 22:09:54 回复(2)

更多回答

～mhui

1，两个数组

2，将其中一个数组进行排列

3，比较两个数组每个值的位置，不一样加1

发表于 2019-02-12 16:59:49 回复(11)

Java

Mono_Chrome

import java.util.Arrays;
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] arr = new int[n];
        int[] arrSorted = new int[n];
        int count = 0;
        for (int i = 0; i < n; i++) {
            int cur = sc.nextInt();
            arr[i] = cur;
            arrSorted[i] = cur;
        }
        Arrays.sort(arrSorted);
        for (int i = 0; i < n; i++) {
            if (arr[i] != arrSorted[i]) {
                count++;
            }
        }
        System.out.println(count);
    }
}

发表于 2019-06-17 17:40:13 回复(0)

Python

华科平凡

python三行

题目介绍WTF？？

实际就是一个很简单的问题，把原始数组排序，对比每一个位置和原来位置是否相同，如果不相同，结果就要加一。

length, original_array = int(input()), list(map(int, input().split()))
sorted_array = sorted(original_array)
print(sum(map(lambda c: original_array[c] != sorted_array[c], range(length))))

编辑于 2019-03-15 21:19:35 回复(0)

元气の悟空

#include<stdio.h>
#include<algorithm>
using namespace std;
int main(){
    int a[100],b[100],n,i,res=0;
    for(scanf("%d",&n),i=0;i<n;i++) scanf("%d",a+i),b[i]=a[i];
    for(sort(a,a+n),i=0;i<n;i++) if(a[i]!=b[i]) res++;
    printf("%d",res);
}

发表于 2017-11-28 23:40:24 回复(0)

tw-luo

//将输入存入两个不同的数组，然后对一个数组排序，最后比较两个数组有多少个位置不一样

#include<iostream>

#include<algorithm>
#include<vector>
using namespace std;
int main(){
    int n,m,sum=0;
    cin >> n;
    vector<int> v1,v2;
    for (int i = 0; i < n; i++){
        cin >> m;
        v1.push_back(m);
        v2.push_back(m);
    }
    sort(v1.begin(), v1.end());
    for (int i = 0; i < n; i++){
        if (v1[i]!=v2[i])
            sum++;
    }
    cout << sum << endl;
    system("pause");
    return 0;
}

发表于 2019-04-21 10:53:52 回复(0)

我是如此相信

    private static int solve(int n, int[] a) {
        int count = 0;
        int[] b = Arrays.copyOf(a, n);
        Arrays.sort(b);
        for (int i = 0; i < n; i++) {
            if (a[i] != b[i]) {
                count++;
            }
        }
        return count;
    }

编辑于 2019-03-21 18:35:36 回复(3)

木然猫猫

水题

n = int(input())
x = list(map(int, input().split()))
sx = sorted(x)
res = 0
for i, j in zip(x, sx):
    res += (i != j)
print(res)

发表于 2019-03-18 17:20:20 回复(0)

C/C++

小陈也只是想要一个实习罢了

1、输入以后，复制一个一样的数组

2、对一个排序，另一个不变

3、对比两个数组有什么区别，对比每一位，有不同则加一

#include<iostream>
#include<algorithm>
using namespace std;
int main(){
    int n,count=0;
    cin>>n;
    int* a=new int[n];
    int* origin=new int[n];
    for(int i=0;i<n;i++){
        cin>>a[i];
        origin[i]=a[i];
    }
    sort(a,a+n);
    for(int i=0;i<n;i++){
        if(origin[i]!=a[i])
            count++;
    }
    cout<<count<<endl;
}

发表于 2019-03-04 16:22:21 回复(0)

C/C++

nbgao

#include <bits/stdc++.h>

using namespace std;

bool cmp(int a, int b){     return a<b; 
}

int main()
{     int n;     while(cin>>n){         int a[n],b[n],cnt=0;         for(int i=0;i<n;i++){             cin>>a[i];             b[i] = a[i];         }         sort(a,a+n,cmp);         for(int i=0;i<n;i++)             if(a[i]!=b[i])                 cnt++;         cout<<cnt<<endl;      }     return 0;
}

发表于 2019-02-03 14:03:31 回复(0)

C/C++

就叫我offer收割机吧

首先定义两个数组，一个用来排序，另一个做参考，对比排序后的两个数组中每个位置的值是否发生变化，若发生变化计数count自增1

#include<iostream>

using namespace std;
int bubble(int a[], int length)
{
    int i, j, tmp, flag = 1;
    for (i = 0; i<length - 1; i++)
    {
        flag = 0;
        for (j = 1; j<length - i; j++)
        {
            if (a[j]<a[j - 1])
            {
                tmp = a[j];
                a[j] = a[j - 1];
                a[j - 1] = tmp;
                flag = 1;
            }
        }
    }
    return 0;
}
int main()
{
    int count = 0;
    int a[50];
        int b[50];
        int n;
        cin >> n;
    for (int i = 0; i < n; i++)
    {
        cin >> a[i];
        b[i] = a[i];
    }
    bubble(a, n);
    for (int i = 0; i < n; i++)
    {
        if (a[i] != b[i])
            count++;
    }
    cout << count;
}

发表于 2019-01-23 16:14:10 回复(0)

向宇回桌

最少的方案，就是直接将数移动到它排序好后的对应的位置。

所以直接统计多少个数不在排序后对应的位置就行了。

import java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        ArrayList arr = new ArrayList();
        for (int i=0; i!=n; i++) {
            arr.add(sc.nextInt());
        }
        ArrayList sortArr = new ArrayList(arr);
        Collections.sort(sortArr);
        int count = 0;
        for (int i=0; i!=n; i++) {
            if (!sortArr.get(i).equals(arr.get(i))) {
                count++;
            }
        }
        System.out.println(count);
    }
}

发表于 2019-01-20 03:20:42 回复(0)

Python

喜欢ctrl的cxk

n = eval(input())
a = list(map(int,input().split()))
b = sorted(a)
count = 0 
for i in range(n):  
    if a[i] != b[i]:
        count += 1 
print(count)

编辑于 2019-01-13 18:47:33 回复(0)

Tendō·Pein

//题目说的不是很清楚，想问的是几个位置的数字变化
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
int main()
{
    int num, x;
    cin >> num;
    vector<int> nums, temp;
    while (num--)
    {
        cin >> x;
        nums.push_back(x);
        temp.push_back(x);
    }
    sort(nums.begin(), nums.end());
    int cnt = 0;
    for (int i = 0; i < nums.size(); i++)
    {
        if (nums[i] != temp[i])
            cnt++;
    }
    cout << cnt << endl;
    return 0;
}

发表于 2019-03-11 13:54:26 回复(0)

小谷围做题家

package main

import (
    "fmt"
    "sort"
)

func main() {
    var n int
    fmt.Scan(&n)
    arr:=make([]int,n)
    for i:=0;i<n;i++{
        fmt.Scan(&arr[i])
    }
    ans:=0
    mock:=make([]int,n)
    copy(mock,arr)
    sort.Ints(mock)
    for i:=0;i<n;i++{
        if arr[i]!=mock[i]{
            ans++
        }
    }
    fmt.Print(ans)
}

发表于 2023-03-21 22:15:51 回复(0)

Python 3

giantye

n = int(input())
arr = list(map(int,input().strip().split()))
ans = sorted(arr)
res = 0
for i,d in enumerate(arr):
    if d != ans[i]:
        res += 1
print(res)

发表于 2021-08-13 20:37:24 回复(0)

mawy610

我还以为是要求逆序数，结果就是比较和排序后的结果变化了几个位置。。总感觉爱奇艺的题有点题意不清

发表于 2020-08-23 13:20:38 回复(0)

JavaScript

小白不黑爱吃糖

const  readline=require('readline');//借助node.js进行在线笔试的输入输出
const rl=readline.createInterface({
    input:process.stdin,
    output:process.stdout
});

var rows=[];
rl.on("line",function(line){
     rows.push(line);//将每次输入的行数据存入
    if(2==rows.length){
        var num=rows[0];
        var s=rows[1];
        var arr=s.split(" ");
        var arr1=s.split(" ");
        arr.sort(function(a,b){//数组排序
            return a-b;
        });
        var sum=0;
        for (var i=0;i<num;i++){
        if(arr1[i]!=arr[i]){
                 sum++;
    }
                  }//end for
         console.log(sum);  
         rows.length=0;//状态重置
    }//end if
   
      });

多行输入参考：https://segmentfault.com/a/1190000010715910

发表于 2020-08-17 14:23:39 回复(0)

牛客694917813号

比较简单的c语言版本

#include<stdio.h>

#include<math.h>

int main()
{
int i, j, n, *a, b[50], output = 0, temp;
while(scanf("%d", &n) != EOF)
{
a = (int *)malloc(sizeof(int)*n);
for(i = 0; i < n; i++)
{
scanf("%d", &a[i]);
b[i] = a[i];
}
for(i = 0; i < n; i++)
{
for(j = i + 1; j < n; j++)
{
if(b[i] > b[j])
{
temp = b[i];
b[i] = b[j];
b[j] = temp;
}
}
if(a[i] != b[i])
output++;
}
printf("%d\n", output);
}
return 0;
}

发表于 2020-03-16 13:54:44 回复(0)

szl201904260905270

为什么缺一个

#include<iostream>
#include<string.h>
using namespace std;
int main()
{
int n,num=0;
int x[105];
memset(x,0,sizeof(x));
while(cin>>n)
{
for(int i=0;i<n;i++)
{
cin>>x[i];
}
for(int i=0;i<n-1;i++)
{
for(int j=i+1;j<n;j++)
{
if(x[i]>x[j])
{
num++;
break;
}
}
}
cout<<num<<endl;
}
return 0;
}

发表于 2019-10-16 19:08:20 回复(0)

提交观点

问题信息

贪心前端工程师爱奇艺 2018 数学排序

来自：爱奇艺2018秋季校招...

上传者：小小

难度：

57条回答 38收藏 9891浏览

通过挑战的用户

查看代码

前端学习中

2022-08-26 10:36:04
孤单又灿烂的神G

2022-07-31 16:08:46
牛客48100...

2022-07-29 09:46:03
牛客64245...

2022-07-01 17:58:21
动态不会规划

2022-06-25 15:58:57

排序

输入描述:

输出描述:

输入

输出

python三行

问题信息

热门推荐

通过挑战的用户

相关试题