【拼多多面试题】实现1-50有序数组中的全部元素随机输出

ゞ浴缸里的玫瑰 2022-01-26 04:39 98阅读 0赞

在 pdd 的面试中遇到让手写一个函数实现：**1-50有序数组中的元素随机输出**。感觉很简单的题目，由于面试官说不可以直接使用 Random ，当时觉得应该就是 Random 的源码实现，但是由于没有看过 Random 的源码，所以一直没想到思路。现在将该题的解题思路记录下来。

*  ### 思路： ###

> 1、从数组的最后一个位置（假设下标是n）开始向前扫描，然后随机生成一个 0 到 n 之间的随机数，假设该随机数是 r1，然后将数组最后一个位置（下标 n）与 r1 位置互换；
> 
> 2、之后开始扫面下一个数（下标为 n - 1），然后随机生成一个 0 到（n - 1） 之间的随机数。假设该随机数是 r2，然后将数组倒数第二个位置（下标为 n - 1）与 r2 位置互换；
> 
> 3、然后继续扫面下一个数（下标为 n - 2），就这样一直迭代下去。

在这个迭代过程中，可以保证扫面点左边的数字都是尚未确定位置的，而右边的数字都是已经安排好位置的。如下图所示使用该算法对数组 \{1,2,3\} 进行乱序：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3Bjd2wxMjA2_size_16_color_FFFFFF_t_70][]

*  ### 代码实现： ###

使用这个思路编写的代码只需要五行，但是需要注意的是：这个方法是会改变原本的数组，如果想原本的数组不被改变，最好先复制一份再将复制品传入这个方法。

package com.bishi.pdd;
    
    import java.util.Arrays;
    import java.util.Random;
    
    public class shuffle {
    
        private static Random random = new Random();
    
        public static <T> void shuffle(T[] arr){
            int length = arr.length;
            // i 代表数组中第多少个数
            for(int i = length; i > 0; i--){
                // 产生一个0-i直接的随机数
                int randIndex = random.nextInt(i);
                // 交换下标为 randIndex 和 i - 1（位置为 i,下标为i-1） 对应的两个数
                swap(arr, randIndex,  i - 1);
            }
        }
    
        public static <T> void swap(T[] arr, int i, int j){
            T temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
        }
    
        public static void main(String[] args) {
            Integer[] arr = {1, 2, 3, 4, 5, 6, 7};
            shuffle(arr);
            System.out.println(Arrays.toString(arr));
        }
    }

其实上面函数的思想在 JDK 中对应的是：Collections.shuffle 函数的实现。只不过 shuffle 函数在 JDK 中的实现是针对集合的。其实，我们可以直接将数组转换成集合后使用 Collections.shuffle 函数，这样也能实现数组中元素的随机输出。

*  # Collections.shuffle 函数的使用 #

package com.bishi.pdd;
    
    import java.util.*;
    
    public class ShuffleDemo {
    
        public static void main(String[] args) {
            List<Integer> list = new ArrayList<Integer>();
            for (int i = 0; i < 10; i++)
                list.add(new Integer(i));
            System.out.println("打乱前:");
            System.out.println(list);
    
            for (int i = 0; i < 5; i++) {
                System.out.println("第" + i + "次打乱：");
                Collections.shuffle(list);
                System.out.println(list);
            }
        }
    }

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3Bjd2wxMjA2_size_16_color_FFFFFF_t_70 1][]

*  ### Collections.shuffle 函数的源码分析 ###

public static void shuffle(List<?> list, Random rnd) {
    	// 集合大小
    	int size = list.size();
    	// 小于shuffle阈值（SHUFFLE_THRESHOLD 等于5）或者可以随机访问(如：ArrayList，访问效率很高)
    	if (size < SHUFFLE_THRESHOLD || list instanceof RandomAccess) { 
    		// 从后往前遍历
    		for (int i = size; i > 1; i--)
    			// 交换指定位置的两个元素
    			swap(list, i - 1, rnd.nextInt(i));
    	} else { // 如果大于阈值并且不支持随机访问，那么需要先转化为数组，再进行处理
    		Object arr[] = list.toArray(); // 该数组只是中间存储过程
    		// 从后往前遍历
    		for (int i = size; i > 1; i--)
    			// 交换指定位置的两个元素
    			swap(arr, i - 1, rnd.nextInt(i));
    		// 重新设置list的值
    		ListIterator it = list.listIterator();
    		// 遍历 List
    		for (int i = 0; i < arr.length; i++) {
    			it.next();
    			it.set(arr[i]);
    		}
    	}
    }

说明：从源码可知，进行 shuffle 时候，是分成两种情况：

1. 若集合元素个数小于 shuffle 阈值或者集合支持随机访问，那么从后往前遍历集合，交换元素。

2. 否则，先将集合转化为数组（提高访问效率），再进行遍历，交换元素（在数组中进行），最后设置集合元素。

其中涉及的 swap 函数如下，两个重载函数：

public static void swap(List<?> list, int i, int j) {
    	// 交换指定位置的两个元素
    	final List l = list;
    	l.set(i, l.set(j, l.get(i)));
    }
    
    private static void swap(Object[] arr, int i, int j) {
    	Object tmp = arr[i];
    	arr[i] = arr[j];
    	arr[j] = tmp;
    }

### 本文参考： ###

1、[https://blog.csdn.net/qq\_33256688/article/details/80304048][https_blog.csdn.net_qq_33256688_article_details_80304048]

2、[https://blog.csdn.net/u013278314/article/details/84170547][https_blog.csdn.net_u013278314_article_details_84170547]

### **如果你有更好的办法，还请留下思路。十分感谢！** ###

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3Bjd2wxMjA2_size_16_color_FFFFFF_t_70]: /images/20220126/6a875649b63440e08467bec13b113e17.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3Bjd2wxMjA2_size_16_color_FFFFFF_t_70 1]: /images/20220126/855f59c2fc91409f9ea13af353d345f7.png
[https_blog.csdn.net_qq_33256688_article_details_80304048]: https://blog.csdn.net/qq_33256688/article/details/80304048
[https_blog.csdn.net_u013278314_article_details_84170547]: https://blog.csdn.net/u013278314/article/details/84170547