风扫地 发表于 2019-5-27 10:56:37

189_旋转数组

/*
给定一个数组，将数组中的元素向右移动 k 个位置，其中 k 是非负数。
示例 1:
输入: 和 k = 3
输出:
解释:
向右旋转 1 步:
向右旋转 2 步:
向右旋转 3 步:
示例 2:
输入: [-1,-100,3,99] 和 k = 2
输出:
解释:
向右旋转 1 步:
向右旋转 2 步:
说明:
尽可能想出更多的解决方案，至少有三种不同的方法可以解决这个问题。
要求使用空间复杂度为 O(1) 的原地算法。
*/

暴力法：
void rotate(int* nums, int numsSize, int k)
{
    int temp = 0;
    int j = 0;
   
    k = k % numsSize;
    while(k--)
    {
      temp = nums;
      for(j = numsSize - 1; j > 0 ;j--)
      {
            nums = nums;
      }
      nums = temp;
    }
}



但很不幸，提交超时了。
/*
33 / 34 个通过测试用例



11939

33 / 34 个通过测试用例
        状态：超出时间限制
       

*/

风扫地 发表于 2019-5-27 10:58:39

改用翻转法
第一步：数组整体翻转
第二步：0～k-1翻转
第三步 : k-1~numsSzie-1翻转

/*
    reverse in nums;
*/
void reverse(int* nums , int left , int right)
{
    int swap_times = (right - left + 1) / 2;
    int i          = 0;
    for(i = 0; i < swap_times ; i++)
    {
      //if((left+i)<(right-i)) /*主要是规避自己与自己交换等于时的异或陷阱,但swap_times已经可以确保,屏蔽此处减少判断*/
      //{
            nums= nums ^ nums;
            nums = nums ^ nums;
            nums= nums ^ nums;
      //}
      //else
      //{
      //    continue;
      //}
    }
}

void rotate(int* nums, int numsSize, int k)
{
    int temp = 0;
    int j = 0;
    k = k % numsSize;
    reverse(nums,0,numsSize-1);
    reverse(nums,0,k-1);
    reverse(nums,k,numsSize-1);
}

测试结果有明显改善。
/*
执行用时 : 24 ms, 在Rotate Array的C提交中击败了83.84% 的用户
内存消耗 : 9 MB, 在Rotate Array的C提交中击败了5.24% 的用户
34 / 34 个通过测试用例
状态：通过
执行用时：32 ms
提交时间：1 分钟之前
*/

风扫地 发表于 2019-5-27 11:34:11

本帖最后由 风扫地 于 2019-5-27 11:36 编辑

把异或交换改成利用中间变量交换，发现效率提高了，"异或交换"比中间值交换效率高这个事吧，遇到了不少反例，异或未必就真的高啊。
执行用时 : 20 ms, 在Rotate Array的C提交中击败了98.82% 的用户 内存消耗 : 9 MB, 在Rotate Array的C提交中击败了5.24% 的用户
页: [1]
查看完整版本: 189_旋转数组