2023-04-16：给定一个长度为N的数组，值一定在0~N-1范围，且每个值不重复比如，arr = [4, 2, 0, 3,

福大大架构师每日一题

发布于 2023-06-08 16:54:19

2770

发布于 2023-06-08 16:54:19

文章被收录于专栏：福大大架构师每日一题福大大架构师每日一题

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
}