目錄

1. 示例1：消失的數字

思路1：等差求和

思路2：異或運算

思路3：排序＋二分查找

2. 示例2：輪轉數組

思路1：逐次輪轉

思路2：三段逆置（經典解法）

思路3：開辟新數組

---

1. 示例1：消失的數字

題目鏈接：

面試題 17.04. 消失的數字 - 力扣（LeetCode）

思路1：等差求和

第一步：0—N利用求和公式計算總和，

第二步：減去數組中的所有元素的值，得到的差值即缺失的元素，

時間復雜度為O(N)；

實現程序如下：

int missingNumber(int* nums, int numsSize) {int N=numsSize;// 0~numsSize共numsSize+1個數字int sum=(0+N)*(N+1)/2;for(int i=0;i<numsSize;i++){sum-=nums[i];}return sum;
}

思路2：異或運算

第一步：用0與數組中所有的數據都異或一遍;

第二步：所得結果再與0—N之間的數字異或一遍；

因為異或與順序無關，存在的數字都異或了兩次，最終結果都是0（同0異1），只有那個0—N之間存在然而數組中不存在的數字經過兩次異或后結果為1，這個數就是缺失的數字。

實現程序如下：

int missingNumber(int* nums, int numsSize) {int x=0;for(int i=0;i<numsSize;i++){x^=nums[i];}for(int j=0;j<numsSize+1;j++){x^=j;}return x;
}

思路3：排序＋二分查找

第一步：將數組元素進行排序，降序升序均可，以升序為例；

第二步：按照0~N的順序依次查找，若下一個數不等于上一個數+1，則下一個數字為消失的數字；

分析時間復雜度：冒泡排序O(N)＋二分查找log N 或 快排O(N)＋二分查找log N二者均不滿足復雜度要求，故不做詳細解釋。

2. 示例2：輪轉數組

題目鏈接：

189. 輪轉數組 - 力扣（LeetCode）

思路1：逐次輪轉

對于N個元素向右輪轉k個位置的輪轉次數分析：

若不考慮輪轉的周期性，則時間復雜度為O(K*N)，（準確為O(K*(N-1))）

但由于數組長度定長，必然存在一些旋轉的周期性問題。

真實旋轉次數為k%=N，

最好的情況為旋轉N的倍數次，即k%N==0，相當于沒有旋轉；

最壞的情況為k%N==N-1（量級為N），故時間復雜度為O(N^2)；

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

存在問題：這種暴力求解的時間復雜度過高：

思路2：三段逆置（經典解法）

對于N個元素向右輪轉k個位置的輪轉，先將前n-k個逆置，再將后k個逆置，最后再整體逆置，即可達到預期輪轉效果。此種情況下，時間復雜度為O(N)。（準確計算為O(2*N)）

實現程序如下：

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);
}

思路3：開辟新數組

額外開辟一個數組，將nums數組后k個元素存放至arr數組前k個位置，將nums數組前numsSize-k個元素存放至arr數組后numsSize-k個位置，再將arr元素依次賦值給nums元素：

#include<string.h>
void rotate(int* nums, int numsSize, int k) {int arr[numsSize];k%=numsSize;int n=numsSize;memcpy(arr, nums+n-k,sizeof(int)*k);memcpy(arr+k,nums,sizeof(int)*(n-k));memcpy(nums,arr,sizeof(int)*n);
}

注：若未采用memcpy，也可使用循環實現逐個拷貝：

void rotate(int* nums, int numsSize, int k) {int arr[numsSize];k%=numsSize;int n=numsSize;// 將nums數組后k個元素存放至arr數組前k個位置for(int i=0;i<=k-1;i++){arr[i]=nums[n-k+i];}// 將nums數組前n-k個元素存放至arr數組后n-k個位置for(int j=0;j<=n-k-1;j++){arr[k+j]=nums[j];}// 將arr元素依次賦值給nums元素for(int x=0;x<=n-1;x++){nums[x]=arr[x];}
}