Simple and Most elegant logic


  • 32

    Let the array be - 123456789 and k = 4

    Step 1 - 12345 6789 ---> 54321 6789

    Step 2 - 54321 6789 ---> 54321 9876

    Step 3 - 543219876 ---> 678912345

    678912345 !!


  • 0
    L

    Thank you so much for this logic. It helps a lot.


  • 0
    J

    mass logic... doode...


  • 2
    L
    class Solution {
    public:
        void rotate(vector<int>& nums, int k) {
    	    int n = nums.size();
    	    k = k % n;
    	    reverse(nums, 0, n - k - 1);
    	    reverse(nums, n - k, n - 1);
    	    reverse(nums, 0, n - 1);
        }
        void reverse(vector<int>& nums, int a, int b) {
            int temp;
            for(int i = a; i < (b + a + 1) / 2; i++) {
    	        temp = nums[i];
    	        nums[i] = nums[a + b - i];
    	        nums[a + b - i] = temp;
            }
        }
    };
    

  • 0
    L

    Comes from the "programming pearls". Nice solution


  • 0
    S

    It's amazing.


  • 0
    K

    Python code based on this logic

    class Solution(object):
        def rotate(self, nums, k):
            """
            :type nums: List[int]
            :type k: int
            :rtype: void Do not return anything, modify nums in-place instead.
            """
            n = len(nums)
            k = k % n
            print("n: ", n, " k: ", k)
            self.reverse(nums, 0, n - k - 1)
            self.reverse(nums, n - k, n - 1)
            self.reverse(nums, 0, n - 1)
    
        def reverse(self, array, a, b):
            while a < b:
                array[a], array[b] = array[b], array[a]
                a += 1
                b -= 1
    
    

  • 0
    N

    it is wonderful!


  • 0
    N

    c++code of this logic

     void rotate(vector<int>& nums, int k) {
            k = k%nums.size();
            reverse(nums.end() - k, nums.end());
            reverse(nums.begin(), nums.end() - k);
    	reverse(nums.begin(), nums.end());
    }
    

  • 0
    G

    I used to ask this question in an interview. Whenever a candidate offered this solution, I'd politely say "That's neat. Now let's come up with a different way to solve the problem" :)

    If that happened, I'd expect an even better solution from them, since it's now clear that they have seen the problem before.


Log in to reply
 

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