目錄

1. 示例1：消失的數(shù)字

思路1：等差求和

思路2：異或運(yùn)算

思路3：排序＋二分查找

2. 示例2：輪轉(zhuǎn)數(shù)組

思路1：逐次輪轉(zhuǎn)

思路2：三段逆置（經(jīng)典解法）

思路3：開辟新數(shù)組

---

1. 示例1：消失的數(shù)字

題目鏈接：

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

思路1：等差求和

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

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

時(shí)間復(fù)雜度為O(N)；

實(shí)現(xiàn)程序如下：

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

思路2：異或運(yùn)算

第一步：用0與數(shù)組中所有的數(shù)據(jù)都異或一遍;

第二步：所得結(jié)果再與0—N之間的數(shù)字異或一遍；

因?yàn)楫惢蚺c順序無關(guān)，存在的數(shù)字都異或了兩次，最終結(jié)果都是0（同0異1），只有那個(gè)0—N之間存在然而數(shù)組中不存在的數(shù)字經(jīng)過兩次異或后結(jié)果為1，這個(gè)數(shù)就是缺失的數(shù)字。

實(shí)現(xiàn)程序如下：

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：排序＋二分查找

第一步：將數(shù)組元素進(jìn)行排序，降序升序均可，以升序?yàn)槔?#xff1b;

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

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

2. 示例2：輪轉(zhuǎn)數(shù)組

題目鏈接：

189. 輪轉(zhuǎn)數(shù)組 - 力扣（LeetCode）

思路1：逐次輪轉(zhuǎn)

對(duì)于N個(gè)元素向右輪轉(zhuǎn)k個(gè)位置的輪轉(zhuǎn)次數(shù)分析：

若不考慮輪轉(zhuǎn)的周期性，則時(shí)間復(fù)雜度為O(K*N)，（準(zhǔn)確為O(K*(N-1))）

但由于數(shù)組長(zhǎng)度定長(zhǎng)，必然存在一些旋轉(zhuǎn)的周期性問題。

真實(shí)旋轉(zhuǎn)次數(shù)為k%=N，

最好的情況為旋轉(zhuǎn)N的倍數(shù)次，即k%N==0，相當(dāng)于沒有旋轉(zhuǎn)；

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

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

存在問題：這種暴力求解的時(shí)間復(fù)雜度過高：

思路2：三段逆置（經(jīng)典解法）

對(duì)于N個(gè)元素向右輪轉(zhuǎn)k個(gè)位置的輪轉(zhuǎn)，先將前n-k個(gè)逆置，再將后k個(gè)逆置，最后再整體逆置，即可達(dá)到預(yù)期輪轉(zhuǎn)效果。此種情況下，時(shí)間復(fù)雜度為O(N)。（準(zhǔn)確計(jì)算為O(2*N)）

實(shí)現(xià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：開辟新數(shù)組

額外開辟一個(gè)數(shù)組，將nums數(shù)組后k個(gè)元素存放至arr數(shù)組前k個(gè)位置，將nums數(shù)組前numsSize-k個(gè)元素存放至arr數(shù)組后numsSize-k個(gè)位置，再將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，也可使用循環(huán)實(shí)現(xiàn)逐個(gè)拷貝：

void rotate(int* nums, int numsSize, int k) {int arr[numsSize];k%=numsSize;int n=numsSize;// 將nums數(shù)組后k個(gè)元素存放至arr數(shù)組前k個(gè)位置for(int i=0;i<=k-1;i++){arr[i]=nums[n-k+i];}// 將nums數(shù)組前n-k個(gè)元素存放至arr數(shù)組后n-k個(gè)位置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];}
}