2023-04-16：给定一个长度为N的数组，值一定在0~N-1范围，且每个值不重复

比如，arr = 4, 2, 0, 3, 1

0 1 2 3 4

把0想象成洞，任何非0数字都可以来到这个洞里，然后在原本的位置留下洞

比如4这个数字，来到0所代表的洞里，那么数组变成 :

arr = 0, 2, 4, 3, 1

也就是原来的洞被4填满，4走后留下了洞

任何数字只能搬家到洞里，并且走后留下洞

通过搬家的方式，想变成有序的，有序有两种形式

比如arr = 4, 2, 0, 3, 1，变成

0, 1, 2, 3, 4或者1, 2, 3, 4, 0都叫有序。

返回变成任何一种有序的情况都可以，最少的数字搬动次数。

来自谷歌。

答案2023-04-16：

解题步骤：

1. 对于第一种有序情况，我们可以模拟交换排序的过程，算出需要交换的次数，具体实现见函数sortArray()。
2. 对于第二种有序情况，我们可以先倒序遍历数组，找出每个数需要移动的最小距离，从而计算出需要移动的次数。
3. 最后比较这两种情况下的最小搬动次数，返回较小值即可。

注意事项：

1. 需要记录每个数是否被遍历过，以防止重复计算。
2. 数字只能搬家到洞里，并且走后留下洞，因此在交换过程中需要记录其中一个数字所在的位置作为洞的位置。

golang代码如下：

package main

import "fmt"

func sortArray(nums []int) int {
    
	// 长度n
	// ans1 : 0 1 2 3 4 .... 这种样子，至少交换几次
	// ans2 : 1 2 3 4 .... 0 这种样子，至少交换几次
	// m : 每个环里有几个数
	// next : 往下跳的位置
	n := len(nums)
	ans1, ans2 := 0, 0
	touched := make([]bool, n)
	// 0 1 2 3 4...
	for i := 0;
     i  n;
 i++ {

		if !touched[i] {

			touched[i] = true
			m := 1
			next := nums[i]
			for next != i {

				m++
				touched[next] = true
				next = nums[next]
			}
    
			// m 当前环，有几个数
			// 6
			// 6
			if m >
 1 {

				if i == 0 {

					ans1 += m - 1
				}
 else {

					ans1 += m + 1
				}

			}

		}

	}
    
	touched = make([]bool, n)
	// 1 2 3 4 ... 0
	// i == n-1
	for i := n - 1;
     i >
    = 0;
 i-- {

		if !touched[i] {
    
			touched[i] = true
			m := 1
			// next
			// 5
			// i(8) ->
     4
			// 0
			// i(8) ->
 n-1
			next := nums[i]
			if next == 0 {

				next = n - 1
			}
 else {

				next--
			}

			for next != i {

				m++
				touched[next] = true
				if nums[next] == 0 {

					next = n - 1
				}
     else if next >
 0 {

					next--
				}
 else {

					next = n - 1
				}

			}
    
			if m >
 1 {

				if i == n-1 {

					ans2 += m - 1
				}
 else {

					ans2 += m + 1
				}

			}

		}

	}

	if ans1  ans2 {

		return ans1
	}

	return ans2
}


func main() {

	nums := []int{
4, 2, 0, 3, 1}

	ans := sortArray(nums)
	fmt.Println(ans) // 输出 3
}
    

rust代码如下：

fn sort_array(nums: &
    [i32]) ->
 i32 {
    
    let n = nums.len() as i32;
    
    let mut ans1 = 0;
    
    let mut ans2 = 0;
    
    let mut touched = vec![false;
     n as usize];


    for i in 0..n {

        if !touched[i as usize] {
    
            touched[i as usize] = true;
    
            let mut m = 1;
    
            let mut next = nums[i as usize];

            while next != i {
    
                m += 1;
    
                touched[next as usize] = true;
    
                next = nums[next as usize];

            }
    

            if m >
 1 {

                if i == 0 {
    
                    ans1 += m - 1;

                }
 else {
    
                    ans1 += m + 1;

                }

            }

        }

    }
    
    touched = vec![false;
     n as usize];


    for i in (0..n).rev() {

        if !touched[i as usize] {
    
            touched[i as usize] = true;
    
            let mut m = 1;

            let mut next = if nums[i as usize] == 0 {

                n - 1
            }
 else {

                nums[i as usize] - 1
            }
    ;

            while next != i {
    
                m += 1;
    
                touched[next as usize] = true;

                next = if nums[next as usize] == 0 {

                    n - 1
                }
 else {

                    nums[next as usize] - 1
                }
    ;

            }
    

            if m >
 1 {

                if i == n - 1 {
    
                    ans2 += m - 1;

                }
 else {
    
                    ans2 += m + 1;

                }

            }

        }

    }


    ans1.min(ans2)
}


fn main() {
    
    let nums = vec![4, 2, 0, 3, 1];
    
    let ans = sort_array(&
    nums);

    println!("{
}
    ", ans);
 // 输出 3
}
    

声明：本文内容由网友自发贡献，本站不承担相应法律责任。对本内容有异议或投诉，请联系2913721942#qq.com核实处理，我们将尽快回复您，谢谢合作！