数组算法题解记录1
1、 26. 删除有序数组中的重复项
1.双指针（初版）
首先注意数组是有序的，那么重复的元素一定会相邻。要求删除重复元素，实际上就是将不重复的元素移到数组的左侧。
考虑用 2 个指针，一个在前记作 p，一个在后记作 q，算法流程如下：
比较 p 和 q 位置的元素是否相等，如果相等，q 后移 1 位；
如果不相等，将 q 位置的元素复制到 p+1 位置上，p 后移一位，q 后移 1 位；
重复上述过程，直到 q 等于数组长度。返回 p + 1，即为新数组长度。
/**
* @param {number[]} nums
* @return {number}
*/
var removeDuplicates = function(nums) {
let p = 0;
let q = 1;
let len = nums.length;
while(q<len){
if(nums[p] === nums[q]) {
q++;
} else {
nums[p+1] = nums[q];
p++;
q++;
}
}
return p+1;
};
2.双指针（优化版）
判断条件合并
如果数组中没有重复元素，按照上面的方法，每次比较时 nums[p] 都不等于 nums[q]，因此就会将 q 指向的元素原地复制一遍，这个操作其实是不必要的。
因此我们可以添加一个小判断，当 q - p > 1 时，才进行复制。
/**
* @param {number[]} nums
* @return {number}
*/
var removeDuplicates = function(nums) {
let p = 0;
let q = 1;
let len = nums.length;
while(q<len){
if(nums[p] !== nums[q]) {
if(q-p>1){
nums[p+1] = nums[q];
}
p++;
}
q++;
}
return p+1;
};
2、寻找数组的中心下标leetcode 724
方法一：前缀和
左侧求和值*2+中心索引处的值=总和
当中心索引左侧或右侧没有元素时，即为零个项相加，这在数学上称作「空和」。在程序设计中我们约定「空和是零」。
/**
* @param {number[]} nums
* @return {number}
*/
var pivotIndex = function(nums) {
let len = nums.length;
let total = 0;
let left = 0;
for(let i = 0; i<len;i++){
total = total + nums[i];
}
for(let i = 0;i<len;i++){
if(left * 2 === total-nums[i]) {
return i;
}
left = left + nums[i];
}
return -1;
};
3、搜索插入位置 leetcode35
1.单纯遍历求解
考虑到要返回插入的位置 pos，它成立的条件为：nums[pos−1]< target ≤ nums[pos]
其中 nums 代表排序数组。由于如果存在这个目标值，我们返回的索引也是 pos，因此我们可以将两个条件合并得出最后的目标：在一个有序数组中找第一个大于等于 target 的下标。
/**
* @param {number[]} nums
* @param {number} target
* @return {number}
*/
var searchInsert = function(nums, target) {
let len = nums.length;
if(nums[len-1] <target) {
return len;
}
for(let i=0; i< len; i++) {
if(nums[i]>=target) {
return i;
}
}
return -1;
};
2.二分查找
/**
* @param {number[]} nums
* @param {number} target
* @return {number}
*/
var searchInsert = function(nums, target) {
const len = nums.length;
let left = 0;
let right = len-1;
let pos = len;
while(left <= right){
let mid = Math.floor((left+right)/2);
if(target <= nums[mid]){
pos = mid;
right = mid-1;
} else {
left = mid+1;
}
}
return pos;
};
4、合并区间 leetcode56
思路
prev 初始为第一个区间，cur 表示当前的区间，res 表示结果数组
开启遍历，尝试合并 prev 和 cur，合并后更新到 prev。合并后的新区间还可能和后面的区间重合，继续尝试合并新的 cur，更新给 prev。直到不能合并（prev[1] < cur[0]），此时将 prev 区间推入 res 数组。
合并的策略
原则上要更新prev[0]和prev[1]，即左右端:
prev[0] = min(prev[0], cur[0])
prev[1] = max(prev[1], cur[1])
但如果先按区间的左端排升序，就能保证 prev[0] < cur[0]
所以合并只需这条： prev[1] = max(prev[1], cur[1])
易错点
我们是先合并，遇到不重合再推入 prev。当考察完最后一个区间，后面没区间了，遇不到不重合的区间，最后的 prev 没推入 res,要单独补上。
/**
* @param {number[][]} intervals
* @return {number[][]}
*/
var merge = function(intervals) {
intervals.sort((a,b) => a[0] - b[0]); // 以“区间开始”升序排序
let prev = intervals[0];
let res = [];
for(let i=0; i<intervals.length; i++){
let cur = intervals[i];
if(prev[1] >= cur[0]) { // 有重合
prev[1] = Math.max(prev[1], cur[1]);
} else {
res.push(prev);
prev = cur;
}
}
res.push(prev); // 补上最后一个prev
return res;
};
5、 217. 存在重复元素
给你一个整数数组 nums 。如果任一值在数组中出现 至少两次 ，返回 true ；如果数组中每个元素互不相同，返回 false 。
/**
* @param {number[]} nums
* @return {boolean}
*/
var containsDuplicate = function(nums) {
let s = new Set();
for(let i=0; i<nums.length; i++) {
let cur = nums[i];
if(s.has(cur)){
return true;
};
s.add(cur);
}
return false;
};
6、136. 只出现一次的数字
给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。
/**
* @param {number[]} nums
* @return {number}
*/
var singleNumber = function(nums) {
let res = 0;
for(let i=0; i<nums.length; i++) {
res = res ^ nums[i];
}
return res;
};
7、 350. 两个数组的交集 II
/**
* @param {number[]} nums1
* @param {number[]} nums2
* @return {number[]}
*/
function getMap(arr){
let map = new Map();
for(let i = 0; i<arr.length; i++) {
let cur = arr[i];
let count = map.get(cur) || 0;
map.set(cur, count + 1);
}
return map;
}
var intersect = function(nums1, nums2) {
let m1 = getMap(nums1);
let res=[];
for(let i=0; i<nums2.length;i++) {
let cur = nums2[i];
let count = m1.get(cur) || 0;
if(count > 0) {
res.push(cur);
m1.set(cur, count-1);
}
}
return res;
};
8、 122. 买卖股票的最佳时机 II
/**
* @param {number[]} prices
* @return {number}
*/
var maxProfit = function(prices) {
let profit = 0
let len = prices.length;
for(let i = 1; i < len; i++) {
let temp = prices[i] - prices[i-1];
if(temp > 0) {
profit = profit + temp;
}
}
return profit;
};
9、 66. 加一
给定一个由 整数 组成的 非空 数组所表示的非负整数，在该数的基础上加一。
最高位数字存放在数组的首位， 数组中每个元素只存储单个数字。
你可以假设除了整数 0 之外，这个整数不会以零开头。
/**
* @param {number[]} digits
* @return {number[]}
*/
var plusOne = function(digits) {
let len = digits.length;
for(let i = len-1;i>=0;i--){
let cur = digits[i];
if(cur < 9){
digits[i]++;
return digits;
}
digits[i] = 0;
}
let arr = [];
arr.push(1);
for(let i= 0; i<digits.length;i++) {
arr.push(digits[i]);
}
return arr;
};
