上一篇最后留了几个问题，都是一些数组的常见面试题，虽然比较简单，但是在面试中可是很常见的，写出解法不难，但是要尽量优化，因为O(n2)的算法肯定是不能打动面试官的哦。
下面就来看一下这几道题目：
1、[LeetCode 27:Remove Element]
给定一个数组nums和一个数值val，将数组中所有等于val的元素删除，并且返回剩余的元素个数。
- 如nums = [3,2,2,3],val = 3;
- 返回2，且nums中前两个元素为[2 2]
对于此题，LeetCode要求我们的空间复杂度为O(1)，也就是说不能申请额外的辅助空间。那么我们只需要遍历一遍数组，将数组中的元素逐一与val比较，如果相同的话，删除即可。
class Solution {
public:
int removeElement(vector<int>& nums, int val) {
for (int i = nums.size() - 1; i >= 0 ; --i) {
if (val == nums[i])
nums.erase(nums.begin() + i);
}
return nums.size();
}
};
这里需要注意的点是：C++的erase删除vector中的元素会导致vector的size发生变化。所以从后往前遍历，遇到相同的删除即可。
2、[LeetCode 26:Remove Duplicated from Sorted Array]
给定一个有序数组，对数组中的元素去重，使得原数组的每个元素只有一个。返回去重后数组的长度值
- 如nums=[1,1,2],
- 结果返回2，且nums数组中元素为[1,2]
因为数组中的元素已经是有序的，所以我们只需要在从后往前遍历数组时，判断当前元素与它前一个元素是不是相等的，如果是相等的话就把此元素删除即可。
public:
int removeDuplicates(vector<int>& nums) {
//因为元素本身有序，因此直接比较前后即可
for(int i = nums.size() - 1; i > 0; --i) {
if(nums[i] == nums[i-1])
nums.erase(nums.begin() + i);
}
return nums.size();
}
};
3、 [LeetCode 80:LeetCode 26:Remove Duplicated from Sorted ArrayII]
给定一个有序数组，对数组中的元素去重，使得原数组的每个元素最多保留两个。返回去重后数组的长度值
- 如nums=[1,1,1,2,2,3],
- 返回5，nums的前5个元素为[1,1,2,2,3]
和上面的题目一样，只不过这次是与它前两个元素比较，如果相同就把它从数组中删除。
class Solution {
public:
int removeDuplicates(vector<int>& nums) {
for(int i = nums.size() - 1; i > 1; --i) {
if(nums[i] == nums[i-2]) {
nums.erase(nums.begin() + i);
}
}
return nums.size();
}
};
4、[LeetCode 88:Merge Sorted Array]
给定两个有序整型数组nums1,nums2,将nums2的元素归并到nums1中。
这道题目有个隐含的信息：nums1的size一定可以装的下nums1和nums2的元素。LeetCode在处理的时候，会传入一个n,一个m。分别表示nums1和nums2的元素个数，并且对于nums1来说，它的内部元素可能会用0来填充空白元素。所以在归并的时候要对它做个处理：
class Solution {
public:
void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
if(nums1.size() < nums2.size())
return;
//首先处理第一个数组
for(int i = nums1.size() - 1; i >= m; --i) {
nums1.erase(nums1.begin() + i);
}
int k = 0;
for(int i = 0; i < nums1.size() && k < n; i++) {
if(nums1[i] >= nums2[k]) {
nums1.insert(nums1.begin() + i,nums2[k++]);
}
}
while(k < n) {
nums1.push_back(nums2[k++]);
}
}
};
这个算法还有优化的空间，感兴趣的同学可以尝试一下。
5、 [LeetCode 215:Kth Largest Element in an Array]
在一个整数序列中寻找第k大的元素
这个题目应该算是挺常见的了吧。解决方法有很多，比如可以先给序列排序(从大到小)然后再取第k个位置的元素。不过既然是取第k大的元素，那么我们能不能不对整个序列都排序就能取得到第k大的元素呢？
可以这样：
1、取最后一个元素为基准数。
2、从第1(下标从0开始)个位置遍历数组，如果遇到比基准数大的就与基准数交换。遍历结束后数组中最大的数就会在基准数的位置。
3、将基准数的位置减一，然后重复做第二部操作k-1次。
这样基准数位置的元素就是我们要找的数了。
class Solution {
public:
int findKthLargest(vector<int>& nums, int k) {
int r = nums.size() - 1;
int count = 0;
while(count < k) {
for(int i = 0; i < r; i++) {
if(nums[i] >= nums[r]) {
swap(nums[i],nums[r]);
}
}
--r;
++count;
}
return nums[nums.size() - k];
}
};
当然还有其他更优化的解法（比如利用快排），希望大家能够提出来一起交流分享一下~
下一篇要介绍对撞指针和滑动窗口。例题在下方，大家可以试着先解一下：
LeetCode 209:Minimum Size Subarray Sum
给定一个整型数组和一个数字S，找到数组中的一个连续子数组，使得连续子数组的数值之和sum>=S，返回此最短的连续子数组的长度。
在实现算法的过程中，我们最好是在得到AC之后继续思考一下还能不能将时间复杂度降低一点，因为如果时间复杂度过高，很可能在笔试的时候不能AC过所有的测试用例(比如牛客的几场笔试题)。
网友评论