a straight-forward solution like drawing lots


  • 0
    H
    public class Solution {
        int[] nums = null;
        Random r = new Random();
        public Solution(int[] nums) {
            this.nums = nums;
        }
        
        /** Resets the array to its original configuration and return it. */
        public int[] reset() {
            return nums;
        }
        
        /** Returns a random shuffling of the array. */
        public int[] shuffle() {
            int length = nums.length;
            int[] result = new int[length];
            int[] indexArray = new int[length];//this array is used to record the chosen position,if chosen,set to 1
            Arrays.fill(indexArray,0);
            for(int i=0;i<length;i++){
                int index = getRandomIndex(length-i,indexArray);//return random index of nums,promised the index is not chosen before
                result[i] = nums[index];//fill the result array with numbers of randomly chosen index 
            }
            return result;
        }
        private int getRandomIndex(int length,int[] array){
            int index = r.nextInt(length);//we can imagine that we put all left numbers into new array,and we randomly choose an index
            int current = -1;
            int newIndex = 0;
            for(int i = 0;i<array.length;i++){
            	if(array[i]==0)//this means the current position is not chosen,so move on,else we shall pass current position and find next available position
            		current++;
            	if(current == index){//if we reach the random index ,stop and return the original index of nums
            		newIndex = i;
            		break;
            	}
            }
            array[newIndex] = 1;//remember to update the record array
            return newIndex;
        }
    }
    
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.