My 21-line simple solution, faster than 87.5%


  • 1
    public class Solution {
        int[] ori;
        int[] ran;
        public Solution(int[] nums) {
            ori = nums;
            ran = new int[nums.length];
            for(int i=0;i<nums.length;i++) ran[i] = nums[i];
        }
        public int[] reset() {
            return ori;
        }
        public int[] shuffle() {
            if(ori.length<2) return ran;
            int a = new Random().nextInt(ori.length);
            int b = new Random().nextInt(ori.length);
            int t = ran[a];
            ran[a] = ran[b];
            ran[b] = t;
            return ran;
        }
    }
    

  • 1
    D

    Shuffling an array is not simply randomly swapping two positions... and of course it is faster than 87.5%.


  • 0

    @dingty Thanks for pointing out.

    I was also not sure about the correctness of the algorithm, while it passed the OJ.

    Can we get a proof of correctness of my algorithm, to say it is a valid/invalid randomization algorithm?


  • 0
    D

    "about the correctness of the algorithm" there is no way to check randomness, only to make sure you are not returning unmodified array every time shuffle gets called.
    "Can we get a proof of correctness of my algorithm," can you show the probability of each element in position i being stored in position j (j can be any position including i) is 1/n?


Log in to reply
 

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