Jimmy小站

小明也有大梦想 — 蒋明/铭
当前位置:网站首页 / 数据结构算法 / 正文

一个无序数组长度为n,所有数字都不一样,并且值都在[0...n-1]范围上 // 返回让这个无序数组变成有序数组的最少交换次数

2021-11-03 / 数据结构算法 / 804 次围观 / 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("测试结束");
    }

}

推荐您阅读更多有关于“逆序对小红书算法,”的文章

[一个Java程序猿的转型之路,读研深造,专注机器学习推荐算法]
额 本文暂时没人评论 来添加一个吧

发表评论

必填

选填

选填

◎欢迎参与讨论,请在这里发表您的看法、交流您的观点。

Copyright © Jimmy小站 Allrights Reserved.备案号:桂ICP备 15005996