面试150——数组字符串

88. 合并两个有序数组

给你两个按 非递减顺序 排列的整数数组 nums1 和 nums2，另有两个整数 m 和 n ，分别表示 nums1 和 nums2 中的元素数目。请你 合并 nums2 到 nums1 中，使合并后的数组同样按 非递减顺序 排列。

倒序比较，避免覆盖

26. 删除有序数组中的重复项

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

27. 移除元素

给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素。元素的顺序可能发生改变。然后返回 nums 中与 val 不同的元素的数量。

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

169. 多数元素

给定一个大小为 n 的数组 nums ，返回其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。

根据以上推论，记数组首个元素为 n1 ，众数为 x ，遍历并统计票数。当发生 票数和 =0 时，剩余数组的众数一定不变 ，这是由于：
当 n1=x ： 抵消的所有数字中，有一半是众数 x 。
当 n1!=x ： 抵消的所有数字中，众数 x 的数量最少为 0 个，最多为一半。
利用此特性，每轮假设发生 票数和 =0 都可以 缩小剩余数组区间 。当遍历完成时，最后一轮假设的数字即为众数。

class Solution {
public:int majorityElement(vector<int>& nums) {int x = 0, votes = 0;for (int num : nums){if (votes == 0) x = num;votes += num == x ? 1 : -1;}return x;}
};