第一行一个正整数n。(1<=n<=5e3) 第二行n个整数 数据保证在int范围内(保证没有重复数字) 输出 从第二个数开始输出每个数插在哪个位置。 样例输入 Copy 5 5 4 3 2 1 样例输出 Copy 0 0 0 0 用java实现

以下是Java代码实现：

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];
        for (int i = 0; i < n; i++) {
            arr[i] = sc.nextInt();
        }
        for (int i = 1; i < n; i++) {
            int j = i - 1;
            int temp = arr[i];
            while (j >= 0 && arr[j] > temp) {
                arr[j + 1] = arr[j];
                j--;
            }
            arr[j + 1] = temp;
            System.out.print(j + 1 + " ");
        }
    }
}

解释：

该程序使用插入排序算法解决问题。遍历数组，将当前元素插入已排序的部分中的正确位置，然后输出该位置的索引。时间复杂度为 O(n^2)。

相关问题

使用插入排序对给定数组从小到大排序，不需要输出排序后的数组，需输出从第二个元素开始每个元素插入的的位置。输入：第一行一个正整数n。(1<=n<=5e3) 第二行n个整数 数据保证在int范围内(保证没有重复数字)。输出：从第二个数开始输出每个数插在哪个位置。Java代码是什么

以下是Java代码实现：

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] nums = new int[n];
        for (int i = 0; i < n; i++) {
            nums[i] = sc.nextInt();
        }
        for (int i = 1; i < n; i++) {
            int temp = nums[i];
            int j = i - 1;
            while (j >= 0 && nums[j] > temp) {
                nums[j + 1] = nums[j];
                j--;
            }
            nums[j + 1] = temp;
            System.out.print(j + 1 + " ");
        }
    }
}

该算法使用插入排序，时间复杂度为$O(n^2)$，空间复杂度为$O(1)$。

对于每个元素，我们将其插入到前面已排序的子数组中。因此，我们需要一个循环来遍历数组中的每个元素，然后将当前元素插入到已排序的子数组中。在插入元素之前，我们需要将已排序的子数组中的所有元素向右移动，为当前元素腾出空间。在向右移动元素时，我们需要注意不要覆盖当前元素。最后，我们将当前元素插入到正确的位置，并输出其插入的位置。

需要注意的是，插入排序是一种稳定的排序算法，它不会改变相同元素的相对位置。因此，对于输入中有相同元素的情况，输出的结果可能会有所不同。

#include<cstdio> #include<cstring> #include<iostream> using namespace std; //1、逆序对：对于给定的一段正整数序列，逆序对就是序列中 ai > aj 且 i < j 的有序对。 //算出给定的一段正整数序列中逆序对的数目。注意序列中可能有重复数字。 int n;//正整数的个数 const int LENGTH = 5e5 + 100; int arr1[LENGTH];//输入的原始正整数序列 int temp[LENGTH];//暂存排序完毕的数 long long cnt = 0; void mergeSort(int a, int b) {//左区间下标一定大于右区间下标，排序不影响比较大小 if (a == b) return; int mid = (a + b) / 2; int i = a, k = a, j = mid + 1; mergeSort(a, mid);//将数组平分为左右两个区间，利用递归、分治的思想将数组分为同规模的更小的问题 mergeSort(j, b); while (i <= mid && j <= b) { //从各区间第一位开始，将左右区间的数进行比较，较小的数存入temp数组 if (arr1[i] <= arr1[j]) { temp[k++] = arr1[i++]; } else { temp[k++] = arr1[j++]; cnt += mid - i + 1;//此时第i位数至第mid位数有序，因此第i位之后的数也大于当前第j位数 } } while (i <= mid) {//当右区间的数都已被比较过，第i位数已经找不到能够进行比较的数，此时只需要把左区间剩下的数存入temp数组中即可 temp[k++] = arr1[i++]; } while (j <= b) {//此处与上面的while循环同理 temp[k++] = arr1[j++]; } for (int k = a; k <= b; ++k) {//最后将排列好的有序数组重新存入m数组中 arr1[k] = temp[k]; } } int main() { cout << "请输入一个正整数序列的个数：" << endl; cin >> n; cout << endl; cout << "请输入该正整数序列，每个整数之间以空格隔开：" << endl; for (int i = 1; i <= n; ++i) { cin >> arr1[i]; } cout << endl; mergeSort(1, n); cout << "该输入的正整数序列中，逆序对的数目为 " << cnt << " 个。" << endl; return 0; }

这是一个使用归并排序求解逆序对的算法实现。整个算法的核心思想是，在归并排序的过程中，每当将一个数字从右侧区间插入到左侧区间时，我们都能够计算出这个数字与左侧区间中剩余数字组成的逆序对个数。具体来说，我们在归并排序过程中，维护两个有序的区间，分别为左区间和右区间。我们从左区间和右区间的首位开始，按照从小到大的顺序比较左右两个区间的数，将较小的数存入一个临时数组中。如果当前比较的两个数分别来自左区间和右区间，则如果左区间的数小于等于右区间的数，则可以直接将左区间的数存入临时数组中；但是如果左区间的数大于右区间的数，则说明左区间当前的数及其之后的数都大于右区间的数，因此需要将右区间的数存入临时数组中，并且计算出当前左区间中剩余的数字与右区间的数组成的逆序对个数。这个个数实际上就是左区间中当前数字之后的数字个数。

最后，当整个归并排序过程结束时，我们就能够得到整个序列中逆序对的个数，即cnt变量的值。这个算法的时间复杂度为O(n log n)，其中n为序列中数字的个数。因此，对于大规模的数据，这个算法仍然是非常高效的。