LeetCode:189. Rotate Array 旋转数组(C语言)

r囧r小猫 2023-07-18 02:26 18阅读 0赞

**题目描述：**  
给定一个数组，将数组中的元素向右移动 k 个位置，其中 k 是非负数。

示例 1:

输入: \[1,2,3,4,5,6,7\] 和 k = 3  
输出: \[5,6,7,1,2,3,4\]  
解释:  
向右旋转 1 步: \[7,1,2,3,4,5,6\]  
向右旋转 2 步: \[6,7,1,2,3,4,5\]  
向右旋转 3 步: \[5,6,7,1,2,3,4\]

示例 2:

输入: \[-1,-100,3,99\] 和 k = 2  
输出: \[3,99,-1,-100\]  
解释:  
向右旋转 1 步: \[99,-1,-100,3\]  
向右旋转 2 步: \[3,99,-1,-100\]

说明:

尽可能想出更多的解决方案，至少有三种不同的方法可以解决这个问题。
    要求使用空间复杂度为 O(1) 的 原地 算法。

**解答 ：**

void rotate(int* nums, int numsSize, int k)
    { 
        int i = 0;
        int j = 0;
        int temp = 0;
        int previous = 0;
        
        for(i = 0;i < k;i++)
        { 
            previous = nums[numsSize - 1];
            for(j = 0; j < numsSize;j++)
            { 
                temp = nums[j];
                nums[j] = previous;
                previous = temp;
            }
        }
    
    }

**运行结果：**  
![在这里插入图片描述][20200323141555608.png]  
**Notes：**  
数组元素移动算法图示如下：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dhbmdxaW5nY2h1YW45Mg_size_16_color_FFFFFF_t_70]![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dhbmdxaW5nY2h1YW45Mg_size_16_color_FFFFFF_t_70 1]

我在第一次提交代后超时，原因可能在对剩余数组元素排序耗时过多：

void rotate(int* nums, int numsSize, int k)
    { 
     	if(0 == k) return;
        
        int i = 0;
        int j = 0;
        int temp = 0;
        
        
        while(k)
        { 
            temp = nums[numsSize - 1];
            
            for(j = numsSize - 1;j > 0 ;j--)
            { 
                nums[j] = nums[j - 1];
            }
            
            nums[0] = temp;        
            
            k--;
        }
    }

[20200323141555608.png]: /images/20230528/58abb732185e4e8d9a0e05ae64b9096a.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dhbmdxaW5nY2h1YW45Mg_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200323142210468.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dhbmdxaW5nY2h1YW45Mg==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dhbmdxaW5nY2h1YW45Mg_size_16_color_FFFFFF_t_70 1]: /images/20230528/e47ee177f7f24bb497858686d3534231.png