Jimmy小站
小明也有大梦想 — 蒋明/铭一个无序数组长度为n,所有数字都不一样,并且值都在[0...n-1]范围上 // 返回让这个无序数组变成有序数组的最少交换次数
2021-11-03 / 数据结构算法 / 3378 次围观 / 0 次吐槽来自小红书,一个无序数组长度为n,所有数字都不一样,并且值都在[0…n-1]范围上,返回让这个无序数组变成有序数组的最少交换次数
代码来来源(方便自己整理笔记,就拿来了) https://github.com/algorithmzuo/publicclass2020/blob/master/src/class060/Code01_MinSwapTimes.java
package class060;
public class Code01_MinSwapTimes {
public static void swap(int[] arr, int i, int j) {
int tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
}
// 已知arr中,只有0~n-1这些值,并且都出现1次
//判断下标i的值是不是i 如不是,则让下标i的值去到数组对应的下标,直到下标=下标对应的值。这样就找到一个环 这时ans的值=环中数量-1 且此时,下标=下标对应的值的位置,就都已经在遍历过的环中。没被遍历到且位置正好的,就是独自成环,不需要交换,直接跳过,直到所有位置的值都与下标相等,则已经全部成环。ans=N-环的个数
public static int minSwap2(int[] arr) {
int ans = 0;
for (int i = 0; i < arr.length; i++) { // i -> i
while (i != arr[i]) {
swap(arr, i, arr[i]);
ans++;
}
}
return ans;
}
// 为了测试
public static int[] randomArray(int len) {
int[] arr = new int[len];
for (int i = 0; i < len; i++) {
arr[i] = i;
}
for (int i = 0; i < len; i++) {
swap(arr, i, (int) (Math.random() * len));
}
return arr;
}
public static void main(String[] args) {
int n = 6;
int testTime = 2000;
System.out.println("测试开始");
for (int i = 0; i < testTime; i++) {
int len = (int) (Math.random() * n) + 1;
int[] arr = randomArray(len);
int ans1 = minSwap1(arr);
int ans2 = minSwap2(arr);
if (ans1 != ans2) {
System.out.println("出错了!");
}
}
System.out.println("测试结束");
}
}
本站所有文章如无特别注明均为原创。作者:吉米酱 ,复制或转载请以超链接形式注明转自 Jimmy小站 。
原文地址《一个无序数组长度为n,所有数字都不一样,并且值都在[0...n-1]范围上 // 返回让这个无序数组变成有序数组的最少交换次数》
原文地址《一个无序数组长度为n,所有数字都不一样,并且值都在[0...n-1]范围上 // 返回让这个无序数组变成有序数组的最少交换次数》
- 上一篇:生产用水管线抢修施工方案
- 下一篇:管道化学清洗方案
本月热文
Copyright © Jimmy小站 Allrights Reserved.备案号:桂ICP备 15005996
额 本文暂时没人评论 来添加一个吧
发表评论