Java O(n), using gcd(n, k)


  • 0
    J
        public void rotate(int[] nums, int k) {
            if (k == 0 || nums.length == 0) return;
            int len = nums.length;
            int times = gcd(len, k);
            for (int start = 0; start < times; start++) {
                int runner = (start + k) % len;
                int lastValue = nums[start];
                while (runner != start) {
                    int tmp = nums[runner];
                    nums[runner] = lastValue;
                    lastValue = tmp;
                    runner = (runner + k) % len;
                }
                nums[start] = lastValue;
            }
        }
        
        private int gcd(int n, int k) { 
            return k == 0 ? n : gcd(k, n % k);
        }
    

Log in to reply
 

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