Inplace bubble o(1) space recursive solution


  • 0
    T
    void rotatespec(vector<int>& nums, int start, int len, int k){
        k = k % len;
        if(len == 0 || len == 1 || k == 0) return;
        if(k <= len-k){//k小于一半,末尾k长度字符串往前冒泡。
            int temp;
            for(int i = 0; i != k; i++){
                temp = nums[start+len-1 -i];
                nums[start+len-1 - i] = nums[start+len-1 - k - i];
                nums[start+len-1 - k - i] = temp;
            }
            rotatespec(nums, start, len-k, k);//一次冒一段后递归
        }
        else{//k大于一半,头部len-k长度字符串往后冒泡。 
            int temp;
            for(int i = 0; i != len-k; i++){
                temp = nums[start + i];
                nums[start + i] = nums[start+len-k + i];
                nums[start+len-k + i] = temp;
            }
            rotatespec(nums,start+len-k, k, 2*k-len);
        }
    }
    
    
    void rotate(vector<int>& nums, int k) {
        rotatespec(nums, 0, nums.size(), k);
    }

Log in to reply
 

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