[数据结构与算法] 【学而时习之】线性表之数组OJ

开发: C++知识库 Java知识库 JavaScript Python PHP知识库人工智能区块链大数据移动开发嵌入式开发工具数据结构与算法开发测试游戏开发网络协议系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑笔记本显卡显示器固态硬盘硬盘耳机手机 iphone vivo oppo 小米华为单反装机图拉丁

-> 数据结构与算法 -> 【学而时习之】线性表之数组OJ -> 正文阅读

[数据结构与算法]【学而时习之】线性表之数组OJ

[线性表–数组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;
    }
};

解法二（位运算）：

首先，我们先来介绍一下异或(^)运算

a b a^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];
            else
                b^=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;
                else
                    return 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;
                else
                    return 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--;
            }
            else
                left++;
        }
        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++]);
            else
                ans.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链接：数据结构

受作者水平所限，如果博客内容有什么纰漏错误，欢迎大家批评指正

如果大家对这些题目有什么好的方法思路，也欢迎大家来和我交流😉