|
| 1 | +packagemedium; |
| 2 | +/**384. Shuffle an Array QuestionEditorial Solution My Submissions |
| 3 | +Total Accepted: 94 |
| 4 | +Total Submissions: 247 |
| 5 | +Difficulty: Medium |
| 6 | +Shuffle a set of numbers without duplicates. |
| 7 | +
|
| 8 | +Example: |
| 9 | +
|
| 10 | +// Init an array with set 1, 2, and 3. |
| 11 | +int[] nums = {1,2,3}; |
| 12 | +Solution solution = new Solution(nums); |
| 13 | +
|
| 14 | +// Shuffle the array [1,2,3] and return its result. Any permutation of [1,2,3] must equally likely to be returned. |
| 15 | +solution.shuffle(); |
| 16 | +
|
| 17 | +// Resets the array back to its original configuration [1,2,3]. |
| 18 | +solution.reset(); |
| 19 | +
|
| 20 | +// Returns the random shuffling of array [1,2,3]. |
| 21 | +solution.shuffle();*/ |
| 22 | +importjava.util.ArrayList; |
| 23 | +importjava.util.LinkedList; |
| 24 | +importjava.util.List; |
| 25 | +importjava.util.Queue; |
| 26 | +importjava.util.Random; |
| 27 | + |
| 28 | +publicclassShuffleAnArray { |
| 29 | + |
| 30 | +publicstaticvoidmain(String...strings){ |
| 31 | +int[]nums =newint[]{1,2,3}; |
| 32 | +Solution_for_this_questiontest =newSolution_for_this_question(nums); |
| 33 | + } |
| 34 | + |
| 35 | +} |
| 36 | +classSolution_for_this_question { |
| 37 | +//Note: the problem states that this is a set without duplicates which makes building all combinations easier |
| 38 | + |
| 39 | +privateList<List<Integer>>combinations; |
| 40 | +privateint[]original; |
| 41 | +privateRandomrandom; |
| 42 | + |
| 43 | +publicSolution_for_this_question(int[]nums) { |
| 44 | +original =nums; |
| 45 | +random =newRandom(); |
| 46 | +combinations =buildAllComb(nums); |
| 47 | + } |
| 48 | + |
| 49 | +//insert next value into all possible positions, I wrote this method myself, of course it could be simplified to not use a queue |
| 50 | +//but it just naturally came into my mind that I used a queue |
| 51 | +privateList<List<Integer>>buildAllComb(int[]nums) { |
| 52 | +List<List<Integer>>result =newArrayList<List<Integer>>(); |
| 53 | +if(nums ==null ||nums.length ==0)returnresult; |
| 54 | + |
| 55 | +List<Integer>list =newArrayList<Integer>(); |
| 56 | +list.add(nums[0]); |
| 57 | +Queue<List<Integer>>q =newLinkedList(); |
| 58 | +q.offer(list); |
| 59 | +for(inti =1;i <nums.length;i++){ |
| 60 | +intqSize =q.size(); |
| 61 | +for(intk =0;k <qSize;k++){ |
| 62 | +List<Integer>currList =q.poll(); |
| 63 | +for(intj =0;j <=currList.size();j++){ |
| 64 | +List<Integer>newL =newArrayList<Integer>(currList); |
| 65 | +newL.add(j,nums[i]); |
| 66 | +q.offer(newL); |
| 67 | + } |
| 68 | + } |
| 69 | + } |
| 70 | +while(!q.isEmpty()){ |
| 71 | +result.add(q.poll()); |
| 72 | + } |
| 73 | +returnresult; |
| 74 | + } |
| 75 | + |
| 76 | +/** Resets the array to its original configuration and return it. */ |
| 77 | +publicint[]reset() { |
| 78 | +returnoriginal; |
| 79 | + } |
| 80 | + |
| 81 | +/** Returns a random shuffling of the array. */ |
| 82 | +publicint[]shuffle() { |
| 83 | +if(original ==null ||original.length ==0)returnoriginal; |
| 84 | +intrandomIndex =random.nextInt(combinations.size()); |
| 85 | +List<Integer>list =combinations.get(randomIndex); |
| 86 | +int[]result =newint[list.size()]; |
| 87 | +for(inti =0;i <list.size();i++){ |
| 88 | +result[i] =list.get(i); |
| 89 | + } |
| 90 | +returnresult; |
| 91 | + } |
| 92 | +} |
| 93 | + |