数组操作的工夫复杂度

  • Access：O(1)
  • Search：O(n)
  • Insert： 均匀O(n)，最好的状况下O(1)，也就是在数组尾部插入O(1)，最坏的状况下O(n)
  • Delete；均匀O(n)，最好的状况下O(1)，也就是在数组尾部删除O(1)，最坏的状况下O(n)

75. 色彩分类 （medium）

给定一个蕴含红色、红色和蓝色、共 n 个元素的数组 nums ，原地对它们进行排序，使得雷同色彩的元素相邻，并依照红色、红色、蓝色顺序排列。

咱们应用整数 0、 1 和 2 别离示意红色、红色和蓝色。

必须在不应用库的sort函数的状况下解决这个问题。

示例 1：

输出：nums = [2,0,2,1,1,0]
输入：[0,0,1,1,2,2]
示例 2：

输出：nums = [2,0,1]
输入：[0,1,2]

提醒：

n == nums.length
1 <= n <= 300
nums[i] 为 0、1 或 2

进阶：

你能够不应用代码库中的排序函数来解决这道题吗？
你能想出一个仅应用常数空间的一趟扫描算法吗？

动画过大，点击查看

办法1.双指针

  • 思路：筹备p0，p1两个指针，p0指向0元素，p1指向1，初始化的时候，两个指针都指向数组的第一个地位。而后循环数组

    1. 遇见1就替换以后元素和p1，让p1加1，向前挪动一位
    2. 遇见0就替换以后元素和p0，如果p1小于p0，则此时p0指向的元素是1，与i地位元素替换之后 这个替换过来的1地位就不对了，所以替换过来的1须要在和p1替换一下，这时p0和p1都指向了正确的元素，所以都须要向前挪动一次。如果p0等于p1，则后面的元素都是0，所以p0和p1也要向前挪动一次
  • 复杂度：工夫复杂度O(n)，n是数组的长度，空间简单O(1)

js：

var sortColors = function (nums) {    let p0 = 0 //指向0    let p1 = 0 //指向0    for (let i = 0; i < nums.length; i++) {        if (nums[i] === 1) {//如果以后i指向的元素等于1，则替换以后元素和p1指向的元素            let temp = nums[p1]            nums[p1] = nums[i]            nums[i] = temp            p1++        } else if (nums[i] === 0) {//如果以后i指向的元素等于0，则替换以后元素和p0指向的元素            let temp = nums[p0]            nums[p0] = nums[i]            nums[i] = temp            //如果p0小于p1 则此时p0指向的元素是1，与i地位元素替换之后 这个替换过来的1地位就不对了 所以替换过来的1须要在和p1替换一下            if (p0 < p1) {                temp = nums[i];                nums[i] = nums[p1];                nums[p1] = temp;            }            //每次替换0之后都要挪动p0和p1，如果p0===p1，则后面都是0，如果p0<p1,后面的代码曾经替换了两次            p0++            p1++        }    }};
办法2.双指针

  • 思路：筹备两指针，p0指向元素0，它右边的都是0，p2指向2，它左边都是2，而后循环数组，当循环到了p2，阐明p2左边的元素都是正确的数，所以i<=p2

    1. 如果此时i指向元素2 i小于p2 则一直替换p2和i指向的元素 因为替换过去的数可能还是2，那这个2就处于不正确的地位了
    2. 如果此时i指向元素0 则替换p0和i指向的元素
    3. 循环实现则0和2都拍好了，两头的1天然也是正确的地位
  • 复杂度：工夫复杂度O(n)，n是数组的长度，空间简单O(1)

js：

var sortColors = function (nums) {    let p0 = 0;//指向0    let p2 = nums.length - 1;//指向2    for (let i = 0; i <= p2; i++) {//当循环到了p2 阐明p2左边的元素都是正确的数，所以i<=p2        //如果此时i指向元素2 i小于p2 则一直替换p2和i指向的元素 因为替换过去的数可能还是2，那这个2就处于不正确的地位了        while (nums[i] === 2 && i < p2) {            let temp = nums[i];            nums[i] = nums[p2];            nums[p2] = temp;            p2--;        }        //如果此时i指向元素0 则替换p0和i指向的元素        if (nums[i] === 0) {            let temp = nums[i];            nums[i] = nums[p0];            nums[p0] = temp;            p0++;        }    }};//写法2var sortColors = function (nums) {    const swap = (list, p1, p2) => [list[p1], list[p2]] = [list[p2], list[p1]]    let red = 0,        blue = nums.length - 1,        p = 0    while (p <= blue) {        switch (nums[p]) {            case 0:                swap(nums, red++, p)                p++                break;            case 1://遇见1 始终让p++ 这样即便替换过去的是2 也是处于正确的地位                p++                break;            case 2:                swap(nums, blue--, p)                break;            default:                break;        }    }};

922. 按奇偶排序数组 II （easy）

给定一个非负整数数组 nums， nums 中一半整数是 奇数 ，一半整数是 偶数 。

对数组进行排序，以便当 nums[i] 为奇数时，i 也是 奇数 ；当 nums[i] 为偶数时， i 也是 偶数 。

你能够返回 任何满足上述条件的数组作为答案 。

示例 1：

输出：nums = [4,2,5,7]
输入：[4,5,2,7]
解释：[4,7,2,5]，[2,5,4,7]，[2,7,4,5] 也会被承受。
示例 2：

输出：nums = [2,3]
输入：[2,3]

提醒：

2 <= nums.length <= 2 * 104
nums.length 是偶数
nums 中一半是偶数
0 <= nums[i] <= 1000

进阶：能够不应用额定空间解决问题吗？

办法1.双指针

  • 思路：循环偶数地位 如果遇到了奇数，而后循环奇数地位 如果遇到了第一个偶数，就交位
  • 复杂度：工夫复杂度O(n)，空间复杂度O(1)

js：

const swap = (nums, i, j) => {    const temp = nums[i];    nums[i] = nums[j];    nums[j] = temp;};var sortArrayByParityII = function(nums) {    const n  = nums.length;    let j = 1;    for (let i = 0; i < n; i += 2) {        if (nums[i] & 1) {//循环偶数地位 如果遇到了奇数            while (nums[j] & 1) {//循环奇数地位 如果遇到了第一个偶数                j += 2;            }            swap(nums, i, j);//交地位换        }    }       return nums;};

217. 存在反复元素 （easy）

给你一个整数数组 nums 。如果任一值在数组中呈现 至多两次 ，返回 true ；如果数组中每个元素互不雷同，返回 false 。

示例 1：

输出：nums = [1,2,3,1]
输入：true
示例 2：

输出：nums = [1,2,3,4]
输入：false
示例 3：

输出：nums = [1,1,1,3,3,4,3,2,4,2]
输入：true

提醒：

1 <= nums.length <= 105
-109 <= nums[i] <= 109

办法1.排序
  • 思路：先排序，而后循环数组，判断相邻元素是否雷同
  • 复杂度：工夫复杂度O(nlogn)，空间复杂度O(logn)，排序须要的栈空间

js：

var containsDuplicate = function(nums) {    nums.sort((a, b) => a - b);//排序    const n = nums.length;    for (let i = 0; i < n - 1; i++) {        if (nums[i] === nums[i + 1]) {//判断相邻元素是否雷同            return true;        }    }    return false;};
办法2.哈希表
  • 思路：循环数组，将元素存入set，判断每个元素是否存在于set中
  • 复杂度：工夫复杂度O(n)，空间复杂度O(n)

js：

var containsDuplicate = function(nums) {    const set = new Set();    for (const x of nums) {        if (set.has(x)) {            return true;        }        set.add(x);    }    return false;};

283. 挪动零 (easy)

给定一个数组 nums，编写一个函数将所有 0 挪动到数组的开端，同时放弃非零元素的绝对程序。

请留神 ，必须在不复制数组的状况下原地对数组进行操作。

示例 1:

输出: nums = [0,1,0,3,12]
输入: [1,3,12,0,0]
示例 2:

输出: nums = [0]
输入: [0]

提醒:

1 <= nums.length <= 104
-231 <= nums[i] <= 231 - 1

进阶：你能尽量减少实现的操作次数吗？

动画过大，点击查看

办法1:两次遍历
  • 思路：遍历数组，定义索引j为数组的第一个地位，遇上非0元素，让j地位上的元素等于这个非0元素，遍历完数组之后，j地位之后的元素全副置为0
  • 复杂度：工夫复杂度O(n)，空间复杂度O(1)

js：

var moveZeroes = function (nums) {    let j = 0;    for (let i = 0; i < nums.length; i++) {        if (nums[i] !== 0) {//遇到非0元素，让nums[j] = nums[i]，而后j++            nums[j] = nums[i];            j++;        }    }    for (let i = j; i < nums.length; i++) {//剩下的元素全是0        nums[i] = 0;    }    return nums;};
办法2:双指针一次遍历
  • 思路：定义left、right指针，right从左往右挪动，遇上非0元素，替换left和right对应的元素，替换之后left++
  • 复杂度：工夫复杂度O(n)，空间复杂度O(1)

js：

var moveZeroes = function(nums) {    let left=0,right=0    while(right<nums.length){        if(nums[right]!==0){//遇上非0元素，替换left和right对应的元素            swap(nums,left,right)            left++//替换之后left++        }        right++    }};function swap(nums,l,r){    let temp=nums[r]    nums[r]=nums[l]    nums[l]=temp}

167. 两数之和 II - 输出有序数组 (easy)

给你一个下标从 1 开始的整数数组 numbers ，该数组已按 非递加顺序排列 ，请你从数组中找出满足相加之和等于指标数 target 的两个数。如果设这两个数别离是 numbers[index1] 和 numbers[index2] ，则 1 <= index1 < index2 <= numbers.length 。

以长度为 2 的整数数组 [index1, index2] 的模式返回这两个整数的下标 index1 和 index2。

你能够假如每个输出 只对应惟一的答案 ，而且你 不能够 重复使用雷同的元素。

你所设计的解决方案必须只应用常量级的额定空间。

示例 1：

输出：numbers = [2,7,11,15], target = 9
输入：[1,2]
解释：2 与 7 之和等于指标数 9 。因而 index1 = 1, index2 = 2 。返回 [1, 2] 。
示例 2：

输出：numbers = [2,3,4], target = 6
输入：[1,3]
解释：2 与 4 之和等于指标数 6 。因而 index1 = 1, index2 = 3 。返回 [1, 3] 。
示例 3：

输出：numbers = [-1,0], target = -1
输入：[1,2]
解释：-1 与 0 之和等于指标数 -1 。因而 index1 = 1, index2 = 2 。返回 [1, 2] 。

提醒：

2 <= numbers.length <= 3 * 104
-1000 <= numbers[i] <= 1000
numbers 按 非递加程序 排列
-1000 <= target <= 1000
仅存在一个无效答案

办法1:二分法
  • 思路：循环数组，从以后元素左边的元素二分查找另一个元素，使他们的和是target
  • 复杂度：工夫复杂度O(nlogn)，遍历数组，每次遍历都进行了二分。空间复杂度O(1)

js：

var twoSum = function (numbers, target) {    let len = numbers.length,        left = 0,        right = len - 1,        mid = 0    for (let i = 0; i < len; ++i) {//循环数组，从左边的元素二分查找另一个元素        left = i + 1        while (left <= right) {            mid = parseInt((right - left) / 2) + left            if (numbers[mid] == target - numbers[i]) {                return [i + 1, mid + 1]            } else if (numbers[mid] > target - numbers[i]) {                right = mid - 1            } else {                left = mid + 1            }        }    }    return [-1, -1]}
办法2:双指针
  • 思路：应以left和right指针，初始别离在数组的两端，而后一直判断两个指针指向的数字之和 和target的大小，和大了 ，right左移一位，和小了，left右移一位
  • 复杂度：工夫复杂度O(n)，数组总共遍历一次。空间复杂度O(1)

js:

var twoSum = function (numbers, target) {    let [left, right] = [0, numbers.length - 1];//左右指针    while (left < right) {//        if (numbers[left] + numbers[right] > target) {//和大了 right左移一位            right--;        } else if (numbers[left] + numbers[right] < target) {//和小了left右移一位            left++;        } else {            return [left + 1, right + 1];        }    }};

350. 两个数组的交加 II （easy）

给你两个整数数组 nums1 和 nums2 ，请你以数组模式返回两数组的交加。返回后果中每个元素呈现的次数，应与元素在两个数组中都呈现的次数统一（如果呈现次数不统一，则思考取较小值）。能够不思考输入后果的程序。

示例 1：

输出：nums1 = [1,2,2,1], nums2 = [2,2]
输入：[2,2]
示例 2:

输出：nums1 = [4,9,5], nums2 = [9,4,9,8,4]
输入：[4,9]

提醒：

1 <= nums1.length, nums2.length <= 1000
0 <= nums1[i], nums2[i] <= 1000

进阶：

如果给定的数组曾经排好序呢？你将如何优化你的算法？
如果 nums1 的大小比 nums2 小，哪种办法更优？
如果 nums2 的元素存储在磁盘上，内存是无限的，并且你不能一次加载所有的元素到内存中，你该怎么办？

办法1:哈希表
  • 思路：统计nums1中各个元素的频次，循环nums2，看nums2中的元素是否在mums1频数哈希表中存在，存在的话退出后果，并且频数减1
  • 复杂度：工夫复杂度O(m+n)，遍历两个数组，哈希表操作复杂度是O(1)。空间复杂度O(min(m,n))对长度小的数组进行哈希。

js：

const intersect = (nums1, nums2) => {    const map = {};    const res = [];    if (nums1.length < nums2.length) {        [nums1, nums2] = [nums2, nums1]    }    for (const num1 of nums1) {//nums1中各个元素的频次        if (map[num1]) {            map[num1]++;        } else {            map[num1] = 1;        }    }    for (const num2 of nums2) { //遍历nums2        const val = map[num2];        if (val > 0) {            //在nums1中            res.push(num2);         //退出res数组            map[num2]--;            //匹配掉一个，就减一个        }    }    return res;};
办法2:双指针
  • 思路：p1，p2双指针指向两数组中的元素，在p1，p2都不越界的状况下开始循环，如果p1指向的元素大，挪动p2，如果p2指向的元素大，挪动p1，遇到雷同则退出入res，挪动两指针
  • 复杂度：工夫复杂度O(mlogm+nlogn)，m、n别离是数组的长度，排序工夫复杂度是O(mlogm+nlogn)，两数组遍历是O(m+n)。空间复杂度O(logm+logn)

js：

const intersect = (nums1, nums2) => {    nums1.sort((a, b) => a - b);    nums2.sort((a, b) => a - b); //排序两个数组    const res = [];    let p1 = 0;//指向nums1中的元素    let p2 = 0;//指向nums2中的元素    while (p1 < nums1.length && p2 < nums2.length) {//不越界条件        if (nums1[p1] > nums2[p2]) {//p1指向的元素大，挪动p2            p2++;        } else if (nums1[p1] < nums2[p2]) {//p2指向的元素大，挪动p1            p1++;        } else {            //遇到雷同则退出入res，挪动两指针            res.push(nums1[p1]);            p1++;            p2++;        }    }    return res;};

349. 两个数组的交加 (easy)

给定两个数组 nums1 和 nums2 ，返回 它们的交加 。输入后果中的每个元素肯定是 惟一 的。咱们能够 不思考输入后果的程序 。

示例 1：

输出：nums1 = [1,2,2,1], nums2 = [2,2]
输入：[2]
示例 2：

输出：nums1 = [4,9,5], nums2 = [9,4,9,8,4]
输入：[9,4]
解释：[4,9] 也是可通过的

提醒：

1 <= nums1.length, nums2.length <= 1000
0 <= nums1[i], nums2[i] <= 1000

办法1：汇合
  • 思路：先将数组转成set，而后遍历长度小的set，判断set1中的元素是否存在于set2中，存在的话就是其中一个交加。
  • 复杂度：工夫复杂度O(m+n)，m，n是两数组的长度，数组转成汇合的工夫复杂度就是数组的长度，遍历寻找交加的复杂度是O(min(m,n))。空间复杂度O(m+n)，就是两个set的空间

js：

var intersection = function (nums1, nums2) {    let set1 = new Set(nums1);    let set2 = new Set(nums2);//数组转成set    if (set1.size > set2.size) {//用size小的数组遍历        [set1, set2] = [set2, set1]    }    const intersection = new Set();    for (const num of set1) {//遍历set1        if (set2.has(num)) {//元素如果不存在于set2中就退出intersection            intersection.add(num);        }    }    return [...intersection];//转成数组};
办法2：排序+双指针

动画过大，点击查看

  • 思路：数组排序，而后用两个指针别离遍历数组，如果两个指针指向的元素相等 就是其中一个交加，否则比拟两个指针指向的元素的大小，较小的向前挪动
  • 复杂度：工夫复杂度O(mlogm+nlogn)，两数组快排工夫复杂度别离是O(mlogm)、O(nlogn)，双指针遍历须要O(m+n)，复杂度取决于较大的O(mlogm+nlogn)。空间复杂度O(logm+logn)排序应用的额定空间

js：

// nums1 = [4,5,9]// nums2 = [4,4,8,9,9]// intersection = [4,9]var intersection = function (nums1, nums2) {    nums1.sort((x, y) => x - y);//排序    nums2.sort((x, y) => x - y);    const length1 = nums1.length,        length2 = nums2.length;    let index1 = 0,//双指针        index2 = 0;    const intersection = [];    while (index1 < length1 && index2 < length2) {//双指针遍历数组        const num1 = nums1[index1],            num2 = nums2[index2];        if (num1 === num2) {//如果两个指针指向的元素相等 就时其中一个交加            //避免反复退出            if (num1 !== intersection[intersection.length - 1]) {                intersection.push(num1);            }            index1++;            index2++;        } else if (num1 < num2) {            index1++;//num1 < num2阐明mums1须要向右挪动        } else {            index2++;//num1 > num2阐明mums1须要向左挪动        }    }    return intersection;};

209. 长度最小的子数组 (medium)

给定一个含有 n 个正整数的数组和一个正整数 target 。

找出该数组中满足其和 ≥ target 的长度最小的 间断子数组 [numsl, numsl+1, ..., numsr-1, numsr] ，并返回其长度。如果不存在符合条件的子数组，返回 0 。

示例 1：

输出：target = 7, nums = [2,3,1,2,4,3]
输入：2
解释：子数组 [4,3] 是该条件下的长度最小的子数组。
示例 2：

输出：target = 4, nums = [1,4,4]
输入：1
示例 3：

输出：target = 11, nums = [1,1,1,1,1,1,1,1]
输入：0

提醒：

1 <= target <= 109
1 <= nums.length <= 105
1 <= nums[i] <= 105

办法1:滑动窗口

动画过大，点击查看

  • 思路：左右指针是滑动窗口的两边，用滑动窗口循环数组，不断扩大窗口，如果窗口中元素的和大于target，就开始放大窗口，而后更新最小滑动窗口
  • 复杂度：工夫复杂度O(n)，数组中的元素都遍历一次，空间复杂度O(1)

js：

var minSubArrayLen = function(target, nums) {    const len = nums.length;    let l = r = sum = 0,         res = len + 1; //最大的窗口不会超过本身长度    while(r < len) {        sum += nums[r++];//扩充窗口        while(sum >= target) {            res = res < r - l ? res : r - l;//更新最小值            sum-=nums[l++];//放大窗口        }    }    return res > len ? 0 : res;};

905. 按奇偶排序数组 (easy)

给你一个整数数组 nums，将 nums 中的的所有偶数元素挪动到数组的后面，后跟所有奇数元素。

返回满足此条件的 任一数组 作为答案。

示例 1：

输出：nums = [3,1,2,4]
输入：[2,4,3,1]
解释：[4,2,3,1]、[2,4,1,3] 和 [4,2,1,3] 也会被视作正确答案。
示例 2：

输出：nums = [0]
输入：[0]

提醒：

1 <= nums.length <= 5000
0 <= nums[i] <= 5000

办法1.排序
  • 思路：排序比拟，偶数在前，奇数在后
  • 复杂度：工夫复杂度O(nlogn)，空间复杂度O(logn)，排序额定的空间

js：

var sortArrayByParity = function(A) {    return A.sort((a, b) => (a & 1) - (b & 1))};
办法2.双指针

  • 思路：右指针从右往左，直到遇到第一个偶数，左指针从左往右，直到遇到第一个奇数，而后替换地位
  • 复杂度：工夫复杂度O(n)，空间复杂度O(1)

js:

var sortArrayByParity = function(A, l = 0, r = A.length - 1) {    while(l !== r) {        while (r > 0 && A[r] & 1) r--        while (l < r && (A[l] & 1) === 0) l++        [A[l], A[r]] = [A[r], A[l]]    }    return A};

27. 移除元素 (easy)

给你一个数组 nums 和一个值 val，你须要 原地 移除所有数值等于 val 的元素，并返回移除后数组的新长度。

不要应用额定的数组空间，你必须仅应用 O(1) 额定空间并 原地 批改输出数组。

元素的程序能够扭转。你不须要思考数组中超出新长度前面的元素。

阐明:

为什么返回数值是整数，但输入的答案是数组呢?

请留神，输出数组是以「援用」形式传递的，这意味着在函数里批改输出数组对于调用者是可见的。

你能够设想外部操作如下:

// nums 是以“援用”形式传递的。也就是说，不对实参作任何拷贝
int len = removeElement(nums, val);

// 在函数里批改输出数组对于调用者是可见的。
// 依据你的函数返回的长度, 它会打印出数组中 该长度范畴内 的所有元素。
for (int i = 0; i < len; i++) {

print(nums[i]);

}

示例 1：

输出：nums = [3,2,2,3], val = 3
输入：2, nums = [2,2]
解释：函数应该返回新的长度 2, 并且 nums 中的前两个元素均为 2。你不须要思考数组中超出新长度前面的元素。例如，函数返回的新长度为 2 ，而 nums = [2,2,3,3] 或 nums = [2,2,0,0]，也会被视作正确答案。
示例 2：

输出：nums = [0,1,2,2,3,0,4,2], val = 2
输入：5, nums = [0,1,4,0,3]
解释：函数应该返回新的长度 5, 并且 nums 中的前五个元素为 0, 1, 3, 0, 4。留神这五个元素可为任意程序。你不须要思考数组中超出新长度前面的元素。

提醒：

0 <= nums.length <= 100
0 <= nums[i] <= 50
0 <= val <= 100

  • 思路：用双指针遍历数组，left初始化在0号地位，right初始化在nums.length的地位，当left<right的时候循环数组

    1. 当nums[left] === val的时候，用right-1的地位笼罩left的地位指向的元素，而后向左挪动right
    2. 当nums[left] !== val的时候，阐明以后元素不须要笼罩，间接让left++
  • 复杂度：工夫复杂度O(n)，数组遍历一遍。空间复杂度O(1)

js：

//办法1//例: [1,2,3,4,5]，  val=1//    [2,3,4,5,5]，  var removeElement = function(nums, val) {    const n = nums.length;    let left = 0;//left指针初始在0号地位    for (let right = 0; right < n; right++) {//用right指针循环数组        if (nums[right] !== val) {//以后元素不为val，则间接笼罩left地位的元素            nums[left] = nums[right];            left++;        }    }    return left;};//优化 题意是能够不思考数组元素的程序//当数组是[1,2,3,4,5]，须要删除的元素是1的时候，如果间接删除，则须要一直将1之后的元素都向前挪动一位//当数组长度很大的时候比拟耗费性能//咱们咱们间接让right初始化在nums.length的地位 left初始化在0号地位//当left<right的时候 循环数组//当nums[left] === val的时候，用right-1的地位笼罩left的地位指向的元素，而后向左挪动right//当nums[left] !== val的时候，阐明以后元素不须要笼罩，间接让left++//例: [1,2,3,4,5]，  val=1//        [5,2,3,4,5]var removeElement = function(nums, val) {    let left = 0, right = nums.length;    while (left < right) {        if (nums[left] === val) {            nums[left] = nums[right - 1];            right--;        } else {            left++;        }    }    return left;};

视频解说：传送门