[線性表–數組OJ] (C/C++實現)

“學而時習之，不亦說乎”

哈嘍又見面啦😁，沿著上篇我們討論的線性表中的順序表，這篇博客，我們講將介紹一些數組OJ題目，學習一些關于數組的操作（騷操作）。

ps: 本節所有代碼實現都是leetcode上的接口型

文章目錄

• • [線性表--數組OJ] (C/C++實現)
  • @[toc]
  • • 1.[leetcode 17.04. 消失的數字](https://leetcode-cn.com/problems/missing-number-lcci/)
    • • **解法一**：掃一遍數組求出實際總和`sum1`，再利用==**等差數列求和公式**==，求出期望的總和`sum2`。
      • **解法二**（==位運算==）：
    • 2.[ 數組中數字出現的次數（leetcode）](https://leetcode-cn.com/problems/shu-zu-zhong-shu-zi-chu-xian-de-ci-shu-lcof/)
    • 3.[ 二分查找（leetcode）](https://leetcode-cn.com/problems/binary-search/)
    • • **3-1.target 定義在[left,right] (==左右都是閉區間的寫法==)**
      • **3.2. target定義在[left,right)的開區間中（==左開右閉區的寫法==）**
    • 4.[移除元素（leetcode）](https://leetcode-cn.com/problems/remove-element/)
    • • **解法一：暴力循環，移動覆蓋** O(N^2)
      • **解法二：雙指針 **O(N)
      • • 快慢指針
        • 左右指針
    • 5.[ 刪除有序數組中的重復項（leetcode）](https://leetcode-cn.com/problems/remove-duplicates-from-sorted-array/)
    • 6.[合并兩個有序數組（leetcode）](https://leetcode-cn.com/problems/merge-sorted-array/)
    • 7.[輪轉數組（leetcode）](https://leetcode-cn.com/problems/rotate-array/)
    • • 解法一（原數組與輪轉數組間的下標關系）：
      • 解法二：三次逆置（個人覺得這個方法超秀😍😍）

1.leetcode 17.04. 消失的數字

題目描述：

數組nums包含從0到n的所有整數，但其中缺了一個。請編寫代碼找出那個缺失的整數。你有辦法在O(n)時間內完成嗎？

示例：nums=[3,0,4,5,7,1,2],n=7 輸出：6

解法一：掃一遍數組求出實際總和sum1，再利用==等差數列求和公式==，求出期望的總和sum2。

sum2-sum1即為缺失的數字。

代碼實現：

class Solution { public:int missingNumber(vector<int>& nums) {int sum1=0;int sum2=(nums.size()+1)*nums.size()/2;for(int i=0;i<nums.size();i++)sum1+=nums[i];return sum2-sum1;} };

解法二（位運算）：

首先，我們先來介紹一下異或(^)運算

aba^b

0	0	0
0	1	1
1	0	1
1	1	0

相同為0，不同為1

例如：a=12,b=9，a的二級制表示：1100，b的二進制表示：1001

a^b為a與b按每一個每一個比特位異或，結果為:0101 ，即12^9=5

易知曉a ^ b=b ^ a，即異或操作滿足交換律

可是這有什么用咧？？？👀👀

由定義我們可以得到一些性質：

0 ^ a = a

a ^ a = 0

由交換律和性質1，2 我們不難證明類似這樣的式子：a ^ b ^ c ^ b ^ c =a

借助位運算我們可以通過如下操作把這道題解決：

把nums數組中的所有元素異或一遍的結果存在ret中

把ret再同1到n的所有數異或一遍，ret即為缺失的數字

因為，經歷了上述操作，1-n出現的數字都異或了兩遍，缺失的數字僅異或了一遍

代碼實現：

class Solution { public:int missingNumber(vector<int>& nums) {int ret=0;for(int i=0;i<nums.size();i++)ret^=nums[i];for(int i=1;i<=nums.size();i++)ret^=i;return ret;} };

---

2. 數組中數字出現的次數（leetcode）

? 接著上一題異或運算的腳步，我們來看一下這道題，對異或運算的進一步運用。

題目描述：

一個整型數組 nums 里除兩個數字之外，其他數字都出現了兩次。請寫程序找出這兩個只出現一次的數字。要求時間復雜度是O(n)，空間復雜度是O(1)。

示例： nums=[1,1,2,3,3,4,5,5] 輸出：[2,4]

如果順著上題我們走過的路徑，我們可能的第一個想法就是，掃一遍數組全部異或一下

但是如果記兩個只出現一次的數字分別為a和b ，最后我們得到的是a^b，根據這個結果我們并不能把a和b分出來。此時我們就遇上難題了。

讓我們看看現在有些什么可以利用的？

a^b的值，這個值雖然不能直接給我們a和b具體是多少，但是可以提供給我們一些關于a和b的性質

通過a^b我們可以獲取a和b二進制表示中不同的那個位（即a ^ b的二進制表示中為1的那個位）

我們通過一個flag加上左移操作便可以找到那個不同的位

這樣我們便可以把數字分為兩組，進行==分組異或==

不難證明：

只出現一次的兩個數一定分到不同的組

兩次出現的數字一定分到相同的組

代碼實現：

class Solution { public:vector<int> singleNumbers(vector<int>& nums) {int val=0,flag=1;for(int i=0;i<nums.size();i++)val^=nums[i];while((val&flag)==0){flag<<=1;}int a=0,b=0;for(int i=0;i<nums.size();i++){if(nums[i]&flag)a^=nums[i];elseb^=nums[i];}return {a,b};} };

---

3. 二分查找（leetcode）

題目描述：

給定一個 n 個元素有序的（升序）整型數組 nums 和一個目標值target ，寫一個函數搜索 nums 中的 target，如果目標值存在返回下標，否則返回 -1。

3-1.target 定義在[left,right] (左右都是閉區間的寫法)

class Solution { public:int search(vector<int>& nums, int target) {int left=0,right=nums.size()-1;while(left<=right){int mid=(left+right)/2;if(nums[mid]>target)right=mid-1;else{if(nums[mid]<target)left=mid+1;elsereturn mid;}}return -1;} }; int middle = left + ((right - left) / 2);// 防止溢出 等同于(left + right)/2

3.2. target定義在[left,right)的開區間中（左開右閉區的寫法）

class Solution { public:int search(vector<int>& nums, int target) {int left=0,right=nums.size();//開區間while(left<right)//等于的情況沒有意義{int mid=(left+right)/2;//可寫成防止溢出的寫法if(nums[mid]>target)//左區間right=mid;else{if(nums[mid]<target)left=mid+1;elsereturn mid;}}return -1;} };

解釋：

①.while循環中判斷條件等于就沒有意義

②.target落在左區間內mid-1可能取到而mid不能取到，所以right=mid

---

4.移除元素（leetcode）

題目描述：

給你一個數組 nums 和一個值 val，你需要 原地 移除所有數值等于 val 的元素，并返回移除后數組的新長度。

不要使用額外的數組空間，你必須僅使用 O(1) 額外空間并 原地 修改輸入數組。

元素的順序可以改變。你不需要考慮數組中超出新長度后面的元素。

解法一：暴力循環，移動覆蓋 O(N^2)

代碼實現：

class Solution { public:int removeElement(vector<int>& nums, int val) {int sz=nums.size();for(int i=0;i<sz;i++){if(val==nums[i]){for(int j=i;j<sz-1;j++)nums[j]=nums[j+1];i--;sz--;}}return sz;} };

！！！注意！！！

第11行的 i - -回退一步非常重要

因為我們沒法判斷用來覆蓋的前一個元素的值是否等于val

這個是用來應對val連續出現的情況

**解法二：雙指針 **O(N)

這里我們介紹兩種雙指針實現方式來完成這一題

快慢指針

思路：

我們開始時使得slow與fast都為0

如果nums[fast] != val 和那么fast和slow一起走，如果fast指的值等于val，fast走而slow不走

每次fast和slow實現一起走的時候，即為把fast指的的值給slow

這樣我們可以證明：fast走完一遍時，0~slow所有的值都不等于val

class Solution { public:int removeElement(vector<int>& nums, int val) {int slow=0;for(int fast=0;fast<nums.size();fast++)if(nums[fast]!=val)nums[slow++]=nums[fast];return slow;} };

左右指針

思路：

left指頭，right指尾

每次當left指的值等于val，left指向的值是必要刪除的，此時我們把right指的值給left，更新right（用尾的元素覆蓋這個必要刪的元素，雖然不能判定尾這個元素是否等于val）

left指的值不等于val，left往前走即可

注意循環的判定條件要取到等（得判定所有的元素）

可以發現：nums中每個元素都判定過，且0~left的所有元素都不等于val

代碼實現：

class Solution { public:int removeElement(vector<int>& nums, int val) {int left=0,right=nums.size()-1;while(left<=right){if(val==nums[left]){nums[left]=nums[right];right--;}elseleft++;}return left;} };

---

5. 刪除有序數組中的重復項（leetcode）

題目描述：

給你一個 升序排列 的數組 nums ，請你原地刪除重復出現的元素，使每個元素 只出現一次 ，返回刪除后數組的新長度。元素的 相對順序 應該保持 一致 。

思路：

升序排列：說明數組中重復出現的元素一定是連續的，不可能間斷

我們用k表示刪除元素（重復元素）的個數，val記錄==上一層循環的nums[i]==

在當前循環層中如果val==nums[i]，說明該層循環nums[i]為重復元素，根據我們在2中給的定義，k需要加1，val可以更新（但沒必要）

當前循環層中的值不等于val,說明這個不是重復元素，i-k位置上的元素即為在[0,i)這個區間中第一個出現重復的元素（1中連續性結合2中定義得出）

示意圖

掃完一遍后，nums.size()-k即為剩下元素的個數，且滿足[0,nums.size()-k]區間上·不存在重復元素。

代碼實現：

class Solution { public:int removeDuplicates(vector<int>& nums) {int k=0,val=nums[0];for(int i=1;i<nums.size();i++){if(val==nums[i]){k++;}else{val=nums[i];nums[i-k]=nums[i];}}return nums.size()-k;} };

---

6.合并兩個有序數組（leetcode）

題目描述：

給你兩個按 非遞減順序 排列的整數數組 nums1 和 nums2，另有兩個整數m和 n ，分別表示 nums1 和 nums2 中的元素數目。

請你 合并 nums2 到 nums1 中，使合并后的數組同樣按 非遞減順序 排列。

思路：

因為兩個數組都排好序，只需同時掃兩個數組，每次把小的放到ans數組中

若m==n掃完一遍后，兩數組按序插入到ans中

如果m != n最后只需把長的數組后面的元素統統放到ans中即可。

(這也是我們后續要寫的==歸并排序==的歸并操作）

代碼實現：

class Solution { public:void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {vector<int> ans;int i=0,j=0;while(i<m&&j<n){if(nums1[i]<nums2[j])ans.push_back(nums1[i++]);elseans.push_back(nums2[j++]);}while(i<m)ans.push_back(nums1[i++]);while(j<n)ans.push_back(nums2[j++]);nums1=ans;} };

---

7.輪轉數組（leetcode）

題目描述：

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

示例：

輸入: 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]

解法一（原數組與輪轉數組間的下標關系）：

如果原數組為nums1[i] ，輪轉后數組為nums2

可知：nums2[ i ] = nums1[ (i+k) % nums1.size() ]

代碼實現：

class Solution { public:void rotate(vector<int>& nums, int k) {int size=nums.size();vector<int> ans(size);for(int i=0;i<size;i++)ans[(i+k)%size]=nums[i];nums=ans;} };

解法二：三次逆置（個人覺得這個方法超秀😍😍）

基本操作：

reverse函數 把1，2，3，4，5完全逆置為5，4，3，2，1（雙指針實現）

此時只需要（記原數組長度為size）：

把[0，size - k % size -1 ]逆置

把[size - k % size, size-1 ]逆置

最后把nums整體再逆置一遍

注意：k要對size取模（輪轉size次相當于轉回來了）

代碼實現：

class Solution { public:void reverse(vector<int>& nums, int begin, int end){int i=begin,j=end;while(i<j){int tmp=nums[i];nums[i]=nums[j];nums[j]=tmp;i++,j--;}}void rotate(vector<int>& nums, int k) {int size=nums.size();reverse(nums,0,size-k%size-1);reverse(nums,size-k%size,size-1);reverse(nums,0,size-1);} };

---

??本篇博客關于數組OJ的內容就到這了

總結一下：我們了解到了位運算，二分查找，數組的插入刪除等操作的運用，雙指針。

希望大家看完能獲得一些啟發，有所收獲

本章節內容所有源碼都會上傳到我的gitee代碼倉庫中，如有需要可前往下載，gitee鏈接：數據結構

受作者水平所限，如果博客內容有什么紕漏錯誤，歡迎大家批評指正

如果大家對這些題目有什么好的方法思路，也歡迎大家來和我交流😉

后續更新鏈表oj(難度up up)和《棧與隊列》

我們下節見😊😊

總結

以上是生活随笔為你收集整理的【绝知此事要躬行】线性表之数组OJ的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。