基础数据结构之——【顺序表】(上)

从今天开始更新数据结构的相关内容。（我更新博文的顺序一般是按照我当前的学习进度来安排，学到什么就更新什么（简单来说就是我的学习笔记），所以不会对一个专栏一下子更新到底，哈哈哈哈哈哈哈！！！😄）

---

本专栏以力扣为落脚点，以实际题目为依据来进行相应知识点的讲解和应用，希望对你能有所帮助！

废话不多说，我们直接开始！

---

---

🔥LC 2057 ----值相等的最小索引(简单)

题目链接：https://leetcode.cn/problems/smallest-index-with-equal-value/

题目简介：

给你一个下标从 0 开始的整数数组 nums ，返回 nums 中满足 i mod 10 == nums[i] 的最小下标 i ；如果不存在这样的下标，返回 -1 。

• x mod y 表示 x 除以 y 的 余数 。

这道题就很简单了，按照题目说的条件，直接线性枚举（可以理解为直接遍历）一遍，就可找出答案。

• 时间复杂度：O(n)
• 空间复杂度：O(1)

代码示例：

class Solution {
public:int smallestEqual(vector<int>& nums) {//获取数组长度int n=nums.size();for(int i=0;i<n;i++){if(i%10==nums[i]) return i;}return -1;}
};

可能会有人问，二分查找行不行，答案是不行！因为nums数组的元素之间并没有特定的联系（是无序的），不适合二分。

既然谈到了，那就简单说说什么是二分吧。

⭐️二分查找（Binary Search）：

是一种在有序数组中查找目标值的算法。它通过将目标值与数组的中间元素进行比较，从而确定目标值可能存在的位置。

下面是一个简单的函数模板：

int firstBadVersion(int *arr,int n) {//定义左右边界，这里我称left和right为游标，而不是指针！避免混淆
int left=-1,right=n;//定义中点
int mid=0;//进行二分
while(right-left>1){//记录中点
mid=left+(right-left)/2;//满足条件时：
if(arr[mid]满足条件){//移动游标
right=mid;
}
//不满足条件时：
else{
left=mid;
}
}
return right;
}

1. 可能有人会问，游标为什么要取-1和n，不能取0和n-1吗？他们的中点不应该一样吗？

   答：其实这是为了避免极端情况的发生，如果左右边界（即0和n-1）满足条件时，二分查找会出错，你可以想想为什么。

2. 换位置时，一定是满足条件时换right吗？

   答：不一定，这个得具体情况具体分析！

---

🔥LC 1464 ----数组中两元素的最大乘积（简单）

题目链接：https://leetcode.cn/problems/maximum-product-of-two-elements-in-an-array/?envType=list&envId=7q99qCXM

题目简介：

给你一个整数数组 nums，请你选择数组的两个不同下标 i 和 j，使 (nums[i]-1)*(nums[j]-1) 取得最大值。
请你计算并返回该式的最大值。

代码示例：

class Solution {
public:int maxProduct(vector<int>& nums) {//这里直接调用sort函数排序：sort(nums.begin(),nums.end());//获取数组长度int len=nums.size();//返回结果return (nums[len-1]-1)*(nums[len-2]-1);}
};

这里我们用到了sort函数，sort函数的时间复杂度通常为O(n log n)，所以我决定写一个O(n)的解法出来：

class Solution {
public:int maxProduct(vector<int>& nums) {int n=nums.size();int max=0;//最大值int maxIndex;//最大值索引int sec=0;//次大值int secIndex;//次大值索引int i,j;//寻找最大值和其索引for(i=0;i<n;i++){if(nums[i]>max) {max=nums[i];maxIndex=i;}}//寻找次大值和其索引for(j=0;j<n;j++){if(j!=maxIndex){if(nums[j]>sec) {        sec=nums[j];   secIndex=j;            }}}int maxSum=(max-1)*(sec-1);return maxSum;}
};

既然用到了sort函数，那就来简单介绍一下：

⭐️sort函数：

是一种常见的排序算法，它能够将一个数组或容器中的元素按照指定的排序规则进行排列。

• 在C++语言中，sort函数在< algorithm >头文件中。
• 基本形式：sort(first,end,comp)

其中，first和last是表示待排序范围的迭代器，comp是一个可选的比较函数，用于指定排序规则。如果不提供comp参数，则默认按照升序排序。要想降序的话，第三个参数可以写成greater<int>()，其中<>里面也可以写double，long，float等等

• 总的来说：
  升序：sort(first,end,cmp)或者sort(first,end)
  降序：sort(first,end,greater<int>()）

---

🔥LC 485----最大连续 1 的个数（简单）

题目链接：https://leetcode.cn/problems/max-consecutive-ones/?envType=list&envId=7q99qCXM

题目简介：

给定一个二进制数组 nums ， 计算其中最大连续 1 的个数。

代码示例：

class Solution {
public:int findMaxConsecutiveOnes(vector<int>& nums) {int n=nums.size();//最长1的个数int maxLenOne=0;//计数器：1出现的个数int countOne=0;for(int i=0;i<n;i++){if(nums[i]==1) countOne++;//计数器：遇1自增else{          maxLenOne= (maxLenOne>countOne)?maxLenOne:countOne;//对长度赋值countOne=0;//计数器归0}}//边界值：可能最后一个数不是0，所以最后一段1的值没有被比较，在此比较一次，防止遗漏最优解maxLenOne= (maxLenOne>countOne)?maxLenOne:countOne;return maxLenOne;}
};

---

🔥LC 27---- 移除元素（简单）

题目链接：https://leetcode.cn/problems/remove-element/?envType=list&envId=7q99qCXM

题目简介：

给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素，并返回移除后数组的新长度。
不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并 原地 修改输入数组。
元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。

代码示例：

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

这里就是一个线性枚举，然后对当前值进行一个判断，如果等于目标值，就将其删除，用到了vector:erase()函数。

⭐️vector中删除元素的方法总结：

vector中删除元素大概有这么几种方法：

• nums.pop_back(); //删除最后一个元素
• nums.clear(); //清空nums中的元素
• nums.erase(nums.begin()+i,nums.begin()+j); //删除nums中从第i+1个元素到第j+1个的所有元素，也就是索引[i,j]。写成nums.erase(nums.begin()+i)就是直接删除第i+1个元素（下标为i）

---

🔥LC 665----非递减数列（中等）

题目链接：https://leetcode.cn/problems/non-decreasing-array/?envType=list&envId=7q99qCXM

题目简介：

给你一个长度为 n 的整数数组 nums ，请你判断在 最多 改变 1 个元素的情况下，该数组能否变成一个非递减数列。
我们是这样定义一个非递减数列的： 对于数组中任意的 i (0 <= i <= n-2)，总满足 nums[i] <= nums[i + 1]。

代码示例：

class Solution {
public:bool checkPossibility(vector<int>& nums) {int n=nums.size();if(n==1 || n==2) return true;int count=0;int count1=0;int count2=0;vector<int>num1(nums);vector<int>num2(nums);for(int i=1;i<n;i++){if(nums[i]<nums[i-1]){                                        nums[i-1]=nums[i];                break; }   }for(int i=1;i<n;i++){if(num1[i]<num1[i-1]){num1[i]=num1[i-1];        break;}    }for(int i=1;i<n;i++){if(num2[i]<num2[i-1]){if(i+1<n){num2[i]=num2[i+1];    break; } else num2[i]=num2[n-2];                         }    }        for(int i=1;i<n;i++){if(num1[i]<num1[i-1]) count1=1;if(nums[i]<nums[i-1]) count=1;if(num2[i]<num2[i-1]) count2=1;if(count==1 && count==1 && count2==1) return false;}  return true;}
};

这道题我用的是枚举的方法，暂时没啥更优化的方法，以后想到了会进行更新！

---