排序

[编程题]排序

热度指数：9236 时间限制：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

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)

Java

(๑‾᷅㉨‾᷅๑)

先进行排序，排序后再与排序前的数组进行对比，看相同索引下的元素是否改变，若改变则count+1；

import java.util.Scanner;
public class Main
{

    public static void main(String[] args)
    {


Scanner input=new Scanner(System.in);
int n=input.nextInt();
int[]data=new int[n];
int[]change=new int[n];
for(int i=0;i<data.length;i++)
{
int a=input.nextInt();
//int temp=a;
          data[i]=a;
change[i]=a;
}

        int count=0;
        int temp;
        for(int i=n-1;i>0;i--)
        {
            for(int j=0;j<i;j++)
            {
                if(data[j]>data[i])
                {
                    temp=data[j];
                    data[j]=data[i];
                    data[i]=temp;
                }

            }

        }
for(int i=0;i<data.length;i++)
            {
                if(data[i]!=change[i])
                {
                    count++;
                }

            }

            System.out.println(count);







    }

}

发表于 2019-05-06 09:20:18 回复(0)

Java

旺旺君

import java.util.Scanner;
import java.util.Arrays;
public class Main{
public static void main(String[] args){
Scanner sc=new Scanner(System.in);
int swap_num=0;
int n=sc.nextInt();
int[] nums1=new int[n];
int[] nums2=new int[n];
for(int i=0;i<n;i++){
nums1[i]=sc.nextInt();
nums2[i]=nums1[i];
}
Arrays.sort(nums1);
for(int i=0;i<n;i++){
if(nums1[i]!=nums2[i])
swap_num++;
}
System.out.println(swap_num);
}

发表于 2019-03-31 19:03:46 回复(0)

Java

雨果伽利略

//思路：
//最少的方案，就是直接将数移动到它排序好后的对应的位置。
//所以直接统计多少个数不在排序后对应的位置就行了。

import java.util.Scanner;
import java.util.Arrays;
public class Main{

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

发表于 2019-02-24 17:04:19 回复(0)

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)