Java随机交换(洗牌)

题目

给定一个整数数组，进行随机交换，要求交换后的数组中每个元素都不在其原来的位置上

思路

1.遍历数组，随机一个不为当前下标的下标，将两个位置的元素交换位置

2.可能会出现某个元素交换多次后又回到原位置的情况，所有需要再遍历一遍数组，如果出现此情况就将交换过的数组再递归交换，直到没有这种情况

答案

注意：数组在交换前需要先拷贝一份，这样才能验证每个元素是否在原位置上

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19


    public static int[] randomSwap(int[] nums){
        int[] arr = nums.clone();
        Random random = new Random();
        for (int i = 0; i < nums.length; i++) {
            int j=i;
            while(j==i){
                j=random.nextInt(nums.length-1);
            }
            int temp =arr[j];
            arr[j]=arr[i];
            arr[i]=temp;
        }
        for (int i = 0; i < nums.length; i++) {
            if (arr[i] == nums[i]) {
                return randomSwap(nums);
            }
        }
        return arr;
    }

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24


import random

def derange_array(array):
    n = len(array)
    result = array[:]
    
    for i in range(n):
        j = i
        while j == i:
            j = random.randint(0, n - 1)
        # 交换元素
        result[i], result[j] = result[j], result[i]
    
    # 确保没有元素在其原来的位置上
    for i in range(n):
        if result[i] == array[i]:
            return derange_array(array)  # 如果有元素在原来位置上就递归交换
    
    return result

# 验证测试
array = [1, 2, 3, 4, 5]
result = derange_array(array)
print(result)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35


import scala.util.Random

object Derangement {
  def main(args: Array[String]): Unit = {
    val array = Array(1, 2, 3, 4, 5)
    val result = derangeArray(array)
    println(result.mkString(", "))
  }

  def derangeArray(array: Array[Int]): Array[Int] = {
    val n = array.length
    val result = array.clone()
    val rand = new Random()

    for (i <- 0 until n) {
      var j = i
      while (j == i) {
        j = rand.nextInt(n)
      }
      // 交换元素
      val temp = result(i)
      result(i) = result(j)
      result(j) = temp
    }

    // 确保没有元素在其原来的位置上
    for (i <- 0 until n) {
      if (result(i) == array(i)) {
        return derangeArray(array) // 如果有元素在原来位置上就递归交换
      }
    }

    result
  }
}