自然数数组的排序

[编程题]自然数数组的排序

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

给定一个长度为N的整形数组arr，其中有N个互不相等的自然数1-N。请实现arr的排序，但是不要把下标 $0 \sim N-1$ 位置上的数通过直接赋值的方式替换成 $1 \sim N$

[要求]

时间复杂度为

，空间复杂度为

备注：

$1\le N \le 10^5$

输入描述:

第一行有一个整数N。表示数组长度
接下来一行有N个互不相等的自然数1-N。

输出描述:

输出N个整数表示排序后的结果

示例1

输入

5
2 1 4 5 3

输出

1 2 3 4 5

备注:

算法知识视频讲解

Java

剑指爪哇岛

这个也不能只写一个方法，太麻烦了。

不断交换，直到遍历完一遍。

import java.util.*;
public class Main{
    
    public static void main(String[] args) {
      Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int[] arr = getArr(n);
        int[] ints = normalSort(arr, n);
        show(ints);
    }
    
    private static int[] normalSort(int[] arr, int n){
        int count = 0;
        while(count < n){
            while (count != arr[count]-1){
                swap(arr,count,arr[count]-1);
            }
            count++;
        }
        return arr;
    }
    private static void swap(int[] arr,int i, int j){
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
    
    private static void show(int[] arr){
        for (int i = 0;i<arr.length;i++){
            System.out.print(arr[i]+" ");
        }
    }
    private static int[] getArr(int n){
        int[] arr = new int[n];
        for(int i = n; i > 0; i--){
            arr[n-i] = i;
        }
        return arr;
    }
}

发表于 2021-09-01 20:46:37 回复(0)

Java

苟或郭嘉生司懿

这题和奇数放在奇数位，偶数放在偶数位的题挺像

//1就是1，2就是2
import java.util.*;

public class Main {
public static void main(String args[])
{
Scanner cin = new Scanner(System.in);
int n;
while(cin.hasNextInt())
{
n = cin.nextInt();
int[] a=new int[n];
for(int i=0;i<n;i++){
a[i]=cin.nextInt();
}
sort(a);
for(int l:a){
System.out.print(l+" ");
}

}
}

public static void sort(int[] a){
for(int i=0;i<a.length;i++){
while(a[i]!=i+1){
swap(a,i,a[i]-1);
}
}
}

public static void swap(int[] arr,int a,int b){
int temp=arr[a];
arr[a]=arr[b];
arr[b]=temp;
}
}

发表于 2020-08-15 08:08:49 回复(0)