湖南网站建设怎么样_私人聊天服务器_百度客服在线咨询人工服务_网络推广培训去哪里好

💐The Begin💐点点关注，收藏不迷路💐

输入n个不相同的正整数，每个数都不超过n。现在需要你把这些整数进行升序排序，每次可以交换两个数的位置，最少需要多少次操作才可以完成排序。

输入

第一行输入n（1≤n≤105）

第二行为n个互不相等且不大于n的正整数。

输出

输出最少交换次数。

样例输入

3
3 2 1

样例输出

1

提示
样例解释：交换3和1

通过遍历数组，检查每个位置上的数是否处于其应该在的位置（按照从小到大排序的正确位置），如果不是，则找到应该在当前位置的那个数的下标，然后交换这两个数的位置，每进行一次这样的交换操作，记录交换次数的变量就加1，最后输出总的交换次数。

C语言实现

#include <stdio.h>
#include <stdlib.h>

#define MAX_N 100005 int n; int arr[MAX_N]; // 存储输入的整数数组

// 找到数组中值为x的元素的下标 int findIndex(int x) {
for (int i = 0; i < n; i++) {
if (arr[i] == x) {
return i;
}
}
return -1; // 正常情况下不会执行到这，只是为了符合函数返回值类型添加 }

int main() {
scanf(“%d”, &n);
for (int i = 0; i < n; i++) {
scanf(“%d”, &arr[i]);
}
int count = 0; // 记录交换次数
for (int i = 0; i < n; i++) {
if (arr[i]!= i + 1) { // 如果当前位置的数不等于其应该在的位置（从小到大排序时的位置）
int index = findIndex(i + 1); // 找到应该在当前位置的数的下标
int temp = arr[i];
arr[i] = arr[index];
arr[index] = temp; // 交换两个数的位置
count++;
}
}
printf(“%d\n”, count);
return 0;
}

C++实现

#include
#include using namespace std;

int main() {
int n;
cin >> n;
vector arr(n); // 使用vector存储输入的整数数组
for (int i = 0; i < n; i++) {
cin >> arr[i];
}
int count = 0; // 记录交换次数
for (int i = 0; i < n; i++) {
if (arr[i]!= i + 1) { // 如果当前位置的数不等于其应该在的位置（从小到大排序时的位置）
int index = 0;
for (int j = 0; j < n; j++) {
if (arr[j] == i + 1) {
index = j;
break;
}
}
swap(arr[i], arr[index]); // 交换两个数的位置
count++;
}
}
cout << count << endl;
return 0;
}

Java实现

import java.util.Scanner;

public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
int[] arr = new int[n];
for (int i = 0; i < n; i++) {
arr[i] = scanner.nextInt();
}
int count = 0; // 记录交换次数
for (int i = 0; i < n; i++) {
if (arr[i]!= i + 1) { // 如果当前位置的数不等于其应该在的位置（从小到大排序时的位置）
int index = 0;
for (int j = 0; j < n; j++) {
if (arr[j] == i + 1) {
index = j;
break;
}
}
int temp = arr[i];
arr[i] = arr[index];
arr[index] = temp; // 交换两个数的位置
count++;
}
}
System.out.println(count);
}
}

Python实现

n = int(input()) arr = list(map(int, input().split())) count = 0 for i
in range(n):
if arr[i]!= i + 1: # 如果当前位置的数不等于其应该在的位置（从小到大排序时的位置）
index = arr.index(i + 1) # 找到应该在当前位置的数的下标
arr[i], arr[index] = arr[index], arr[i] # 交换两个数的位置
count += 1 print(count)

💐The End💐点点关注，收藏不迷路💐