leetcode-384-打亂數組(shuffle an array)-java

題目及測試

package pid384;
/* Shuffle an Array

打亂一個沒有重複元素的數組。

示例:

// 以數字集合 1, 2 和 3 初始化數組。
int[] nums = {1,2,3};
Solution solution = new Solution(nums);

// 打亂數組 [1,2,3] 并傳回結果。任何 [1,2,3]的排列傳回的機率應該相同。
solution.shuffle();

// 重設數組到它的初始狀态[1,2,3]。
solution.reset();

// 随機傳回數組[1,2,3]打亂後的結果。
solution.shuffle();



*/




public class main {
	
	public static void main(String[] args) {
		int[][] testTable = {{1,2,3},{2,7,9,3,1},{7,10,4,3,1},{11,6,2,7}};
		for (int[] ito : testTable) {
			test(ito);
		}
	}
		 
	private static void test(int[] ito) {
		Solution solution = new Solution(ito);
		int[] rtn;
		long begin = System.currentTimeMillis();
		for (int i = 0; i < ito.length; i++) {
		    System.out.print(ito[i]+" ");		    
		}
		System.out.println();
		//開始時列印數組
		
		rtn = solution.shuffle();//執行程式
		long end = System.currentTimeMillis();	
		
		System.out.println(ito + ": rtn=" );
		System.out.println( " rtn=" );
		for (int i = 0; i < rtn.length; i++) {
		    System.out.print(rtn[i]+" ");
		}//列印結果幾數組
		
		rtn = solution.reset();//執行程式
		
		System.out.println(ito + ": rtn=" );
		System.out.println( " rtn=" );
		for (int i = 0; i < rtn.length; i++) {
		    System.out.print(rtn[i]+" ");
		}//列印結果幾數組
		
		System.out.println();
		System.out.println("耗時：" + (end - begin) + "ms");
		System.out.println("-------------------");
	}

}

           

解法1（成功，282ms，較慢）

在class中設定一個int數組作為源頭

reset方法，傳回一個copy的數組

shuffle方法，将源頭數組一個個加入linkedlist

int index=(int)(Math.random()*i);

每次将list的這個index的數字取出加入結果數組

然後i–

package pid384;

import java.lang.reflect.Array;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;

class Solution {

	int[] source;
	
    public Solution(int[] nums) {
        source=nums;
    }
    
    /** Resets the array to its original configuration and return it. */
    public int[] reset() {
        int[] result=Arrays.copyOf(source,source.length);    	
    	return result;
    }
    
    /** Returns a random shuffling of the array. */
    public int[] shuffle() {
        List<Integer> list=new LinkedList<>();
        int length=source.length;
        if(length==0){
        	return null;
        }
        int[] result=new int[length];
        
        for(int i=0;i<length;i++){
        	list.add(source[i]);
        }
        for(int i=length;i>0;i--){
        	int index=(int)(Math.random()*i);
        	result[length-i]=list.get(index);
        	list.remove(index);
        }
        
        
    	return result;
    }
}

/**
 * Your Solution object will be instantiated and called as such:
 * Solution obj = new Solution(nums);
 * int[] param_1 = obj.reset();
 * int[] param_2 = obj.shuffle();
 */

           

解法2（成功，305s，較慢）

速度為O(n)

複制到一個新數組，根據交換，進行随機

Fisher-Yates 洗牌算法跟暴力算法很像。在每次疊代中，生成一個範圍在目前下标到數組末尾元素下标之間的随機整數。接下來，将目前元素和随機選出的下标所指的元素互相交換 - 這一步模拟了每次從 “帽子” 裡面摸一個元素的過程，其中選取下标範圍的依據在于每個被摸出的元素都不可能再被摸出來了。此外還有一個需要注意的細節，目前元素是可以和它本身互相交換的 - 否則生成最後的排列組合的機率就不對了。

class Solution {

	int[] value;
	
    public Solution(int[] nums) {
        value=nums;
    }
    
    /** Resets the array to its original configuration and return it. */
    public int[] reset() {       
    	return value;
    }
    
    /** Returns a random shuffling of the array. */
    public int[] shuffle() {
        int length=value.length;
        if(length==0||length==1){
        	return value;
        }
        int[] result=new int[length];
        System.arraycopy(value, 0, result, 0, length);
        
        for(int i=length-1;i>=0;i--){
        	int index=(int)Math.floor(Math.random()*(i+1));
        	int temp=result[index];
        	result[index]=result[i];
        	result[i]=temp;
        }
    	
    	return result;
    }
}
           

解法3（别人的）

與解法2很像，但是打亂時不用複制一個新數組，代價是空間增加一個數組

class Solution {
    private int[] array;
    private int[] original;

    Random rand = new Random();

    private int randRange(int min, int max) {
        return rand.nextInt(max - min) + min;
    }

    private void swapAt(int i, int j) {
        int temp = array[i];
        array[i] = array[j];
        array[j] = temp;
    }

    public Solution(int[] nums) {
        array = nums;
        original = nums.clone();
    }
    
    public int[] reset() {
        array = original;
        original = original.clone();
        return original;
    }
    
    public int[] shuffle() {
        for (int i = 0; i < array.length; i++) {
            swapAt(i, randRange(i, array.length));
        }
        return array;
    }
}