C語言怎么解決輪轉數組問題

本篇內容主要講解“C語言怎么解決輪轉數組問題”，感興趣的朋友不妨來看看。本文介紹的方法操作簡單快捷，實用性強。下面就讓小編來帶大家學習“C語言怎么解決輪轉數組問題”吧!

題目

1.題目描述

給你一個數組，將數組中的元素向右輪轉 k 個位置，其中 k 是非負數。

示例 1:

輸入:

nums = [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.要求

進階：

• 盡可能想出更多的解決方案，至少有 三種 不同的方法可以解決這個問題。

• 你可以使用空間復雜度為 O(1) 的 原地 算法解決這個問題嗎？

3.原題鏈接

 189. 輪轉數組 - 力扣（LeetCode） (leetcode-cn.com)

二、相關知識點

本題實際上涉及到了復雜度的問題，包括時間復雜度和空間復雜度。

三、解決思路

旋轉法

最優思路，這需要我們有較好的理解力了，可以把數組分為三個部分

假設我們需要選擇k個數字：

1.后k個數字逆置

2.前n-k個數字逆置

3.整體逆置

此方法為最優法。符合題目要求

以示例 1為例子說明：

1 2 3 4 5 6 7//旋轉3個數字
1 2 3 4 7 6 5//后k個數字逆置
4 3 2 1 7 6 5//前n-k個數字逆置
5 6 7 1 2 3 4//整體逆置

源代碼如下：

void reverse(int*nums,int left,int right)
{
    while(left<right)
    {
        int tmp = nums[left];
        nums[left]=nums[right];
        nums[right] = tmp;
        ++left;
        --right;
    }
}
void rotate(int* nums, int numsSize, int k){
    k%=numsSize;
    reverse(nums,0,numsSize-k-1);
    reverse(nums,numsSize-k,numsSize-1);
    reverse(nums,0,numsSize-1);
}

注意點：k的大小可能大于數組的大小，所以我們要取模！

這個算法的時間復雜度為O（N），空間復雜度為O（1）

附上結果運行圖：

直接法

看到這道題，我們的第一種想法就是直接去旋轉，當k=1是。我們就直接把最后一位的數字移動第一位，然后第二位開始往后移動，我們可以創建一個臨時的變量來記錄當前的最后一位，當k很大時，我們自然就是用循環去做，這是每個人都能想得到的一種方法

代碼如下

void rotate(int* nums, int numsSize, int k){
    k %=numsSize;
  while(k--){
      int tmp = nums[numsSize-1];
      for(int end = numsSize-2;end>=0;--end){
          nums[end+1] = nums[end];
      }
      nums[0] = tmp;
  }
}

遺憾的是，這種算法的空間復雜（k*N），沒能跑得過去，超時了，給出運行結果圖

空間換取時間

以空間換取時間，這是比較常見的，就是額外開辟一個數組，存放選擇的幾個數字，然后將之前的數據存儲到該數組的后半部分。最后將新數組拷貝到原來的數組中

代碼如下

void rotate(int* nums, int numsSize, int k){
   k %= numsSize;
   int *newnum = (int*)malloc(sizeof(int)*numsSize);
   int j = 0;
   for(int i =numsSize-k;i<numsSize;i++){
       newnum[j++] =nums[i];
   }
   for(int i = 0;i<numsSize-k;i++){
       newnum[i+k] = nums[i];
   }
   memcpy(nums,newnum,sizeof(int)*numsSize);
}

運行結果如圖

到此，相信大家對“C語言怎么解決輪轉數組問題”有了更深的了解，不妨來實際操作一番吧！這里是億速云網站，更多相關內容可以進入相關頻道進行查詢，關注我們，繼續學習！