大厂算法面试之 leetcode 精讲 19. 数组

作者：全栈潇晨

2021 年 12 月 04 日
本文字数：12360 字
阅读完需：约 41 分钟

搞定大厂算法面试之 leetcode 精讲 19.数组

视频讲解（高效学习）:点击学习

数组操作的时间复杂度

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

283. 移动零 (easy)

动画过大，点击查看

方法 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;};

复制代码

java：

class Solution {  public void moveZeroes(int[] nums) {    if(nums==null) {      return;    }    int j = 0;    for(int i=0;i<nums.length;++i) {      if(nums[i]!=0) {        nums[j++] = nums[i];      }    }    for(int i=j;i<nums.length;++i) {      nums[i] = 0;    }  }}

复制代码

方法 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}

复制代码

java：

class Solution {  public void moveZeroes(int[] nums) {    if(nums==null) {      return;    }    int j = 0;    for(int i=0;i<nums.length;i++) {      if(nums[i]!=0) {        int tmp = nums[i];        nums[i] = nums[j];        nums[j++] = tmp;      }    }  }}

复制代码

75. 颜色分类（medium）

动画过大，点击查看

方法 1.双指针

思路：准备 p0，p1 两个指针，p0 指向 0 元素，p1 指向 1，初始化的时候，两个指针都指向数组的第一个位置。然后循环数组
遇见 1 就交换当前元素和 p1，让 p1 加 1，向前移动一位
遇见 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++        }    }};

复制代码

java

class Solution {    public void sortColors(int[] nums) {        int n = nums.length;        int p0 = 0, p1 = 0;        for (int i = 0; i < n; ++i) {            if (nums[i] == 1) {                int temp = nums[i];                nums[i] = nums[p1];                nums[p1] = temp;                ++p1;            } else if (nums[i] == 0) {                int temp = nums[i];                nums[i] = nums[p0];                nums[p0] = temp;                if (p0 < p1) {                    temp = nums[i];                    nums[i] = nums[p1];                    nums[p1] = temp;                }                ++p0;                ++p1;            }        }    }}

复制代码

方法 2.双指针

思路：准备两指针，p0 指向元素 0，它左边的都是 0，p2 指向 2，它右边都是 2，然后循环数组，当循环到了 p2，说明 p2 右边的元素都是正确的数，所以i<=p2
如果此时 i 指向元素 2 i 小于 p2 则不断交换 p2 和 i 指向的元素因为交换过来的数可能还是 2，那这个 2 就处于不正确的位置了
如果此时 i 指向元素 0 则交换 p0 和 i 指向的元素
循环完成则 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;        }    }};

复制代码

java

class Solution {    public void sortColors(int[] nums) {        int n = nums.length;        int p0 = 0, p2 = n - 1;        for (int i = 0; i <= p2; ++i) {            while (i <= p2 && nums[i] == 2) {                int temp = nums[i];                nums[i] = nums[p2];                nums[p2] = temp;                --p2;            }            if (nums[i] == 0) {                int temp = nums[i];                nums[i] = nums[p0];                nums[p0] = temp;                ++p0;            }        }    }}
//写法2public class Solution {    public void sortColors(int[] nums) {        int len = nums.length;        if (len < 2) {            return;        }
        int red = 0;        int blue = len;        int p = 0;              while (p < blue) {            if (nums[p] == 0) {                swap(nums, p, red);                red++;                p++;            } else if (nums[p] == 1) {                p++;            } else {                blue--;                swap(nums, p, blue);            }        }    }
    private void swap(int[] nums, int index1, int index2) {        int temp = nums[index1];        nums[index1] = nums[index2];        nums[index2] = temp;    }}

复制代码

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

方法 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]}

复制代码

java：

class Solution {    public int[] twoSum(int[] numbers, int target) {        for (int i = 0; i < numbers.length; ++i) {            int left = i + 1, right = numbers.length - 1;            while (left <= right) {                int mid = (right - left) / 2 + left;                if (numbers[mid] == target - numbers[i]) {                    return new int[]{i + 1, mid + 1};                } else if (numbers[mid] > target - numbers[i]) {                    right = mid - 1;                } else {                    left = mid + 1;                }            }        }        return new int[]{-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];        }    }};

复制代码

java

class Solution {    public int[] twoSum(int[] numbers, int target) {        int left = 0, right = numbers.length - 1;        while (left < right) {            int sum = numbers[left] + numbers[right];            if (sum == target) {                return new int[]{left + 1, right + 1};            } else if (sum < target) {                ++left;            } else {                --right;            }        }        return new int[]{-1, -1};    }}

复制代码

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

方法 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;};

复制代码

java：

class Solution {    public int minSubArrayLen(int s, int[] nums) {        int left = 0;        int sum = 0;        int res = Integer.MAX_VALUE;        for (int right = 0; right < nums.length; right++) {            sum += nums[right];            while (sum >= s) {                res = Math.min(res, right - left + 1);                sum -= nums[left++];            }        }        return res == Integer.MAX_VALUE ? 0 : res;    }}

复制代码

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

方法 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];//转成数组};

复制代码

java：

class Solution {    public int[] intersection(int[] nums1, int[] nums2) {        Set<Integer> set1 = new HashSet<Integer>();        Set<Integer> set2 = new HashSet<Integer>();        for (int num : nums1) {            set1.add(num);        }        for (int num : nums2) {            set2.add(num);        }        return getIntersection(set1, set2);    }
    public int[] getIntersection(Set<Integer> set1, Set<Integer> set2) {        if (set1.size() > set2.size()) {            return getIntersection(set2, set1);        }        Set<Integer> intersectionSet = new HashSet<Integer>();        for (int num : set1) {            if (set2.contains(num)) {                intersectionSet.add(num);            }        }        int[] intersection = new int[intersectionSet.size()];        int index = 0;        for (int num : intersectionSet) {            intersection[index++] = 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;};

复制代码

Java；

class Solution {    public int[] intersection(int[] nums1, int[] nums2) {        Arrays.sort(nums1);        Arrays.sort(nums2);        int length1 = nums1.length, length2 = nums2.length;        int[] intersection = new int[length1 + length2];        int index = 0, index1 = 0, index2 = 0;        while (index1 < length1 && index2 < length2) {            int num1 = nums1[index1], num2 = nums2[index2];            if (num1 == num2) {                if (index == 0 || num1 != intersection[index - 1]) {                    intersection[index++] = num1;                }                index1++;                index2++;            } else if (num1 < num2) {                index1++;            } else {                index2++;            }        }        return Arrays.copyOfRange(intersection, 0, index);    }}

复制代码

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

方法 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;};

复制代码

java：

class Solution {    public int[] intersect(int[] nums1, int[] nums2) {        if (nums1.length > nums2.length) {            return intersect(nums2, nums1);        }        Map<Integer, Integer> map = new HashMap<Integer, Integer>();        for (int num : nums1) {            int count = map.getOrDefault(num, 0) + 1;            map.put(num, count);        }        int[] intersection = new int[nums1.length];        int index = 0;        for (int num : nums2) {            int count = map.getOrDefault(num, 0);            if (count > 0) {                intersection[index++] = num;                count--;                if (count > 0) {                    map.put(num, count);                } else {                    map.remove(num);                }            }        }        return Arrays.copyOfRange(intersection, 0, index);    }}

复制代码

方法 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;};

复制代码

java：

class Solution {    public int[] intersect(int[] nums1, int[] nums2) {        Arrays.sort(nums1);        Arrays.sort(nums2);        int length1 = nums1.length, length2 = nums2.length;        int[] intersection = new int[Math.min(length1, length2)];        int p1 = 0, p2 = 0, index = 0;        while (p1 < length1 && p2 < length2) {            if (nums1[p1] < nums2[p2]) {                p1++;            } else if (nums1[p1] > nums2[p2]) {                p2++;            } else {                intersection[index] = nums1[p1];                p1++;                p2++;                index++;            }        }        return Arrays.copyOfRange(intersection, 0, index);    }}

复制代码

27. 移除元素 (easy)

思路：用双指针遍历数组，left 初始化在 0 号位置，right 初始化在nums.length的位置，当left<right的时候循环数组
当nums[left] === val的时候，用 right-1 的位置覆盖 left 的位置指向的元素，然后向左移动 right
当 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;};

复制代码

java：

class Solution {    public int removeElement(int[] nums, int val) {        int n = nums.length;        int left = 0;        for (int right = 0; right < n; right++) {            if (nums[right] != val) {                nums[left] = nums[right];                left++;            }        }        return left;    }}
//优化class Solution {    public int removeElement(int[] nums, int val) {        int left = 0;        int right = nums.length;        while (left < right) {            if (nums[left] == val) {                nums[left] = nums[right - 1];                right--;            } else {                left++;            }        }        return left;    }}

复制代码

217. 存在重复元素（easy）

方法 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;};

复制代码

java：

class Solution {    public boolean containsDuplicate(int[] nums) {        Arrays.sort(nums);        int n = nums.length;        for (int 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;};

复制代码

java：

class Solution {    public boolean containsDuplicate(int[] nums) {        Set<Integer> set = new HashSet<Integer>();        for (int x : nums) {            if (!set.add(x)) {                return true;            }        }        return false;    }}

复制代码

238. 除自身以外数组的乘积 (medium)

思路：从左往右遍历，记录从左到当前位置前一位的乘积，然后从右往左遍历，从左到当前位置前一位的乘积乘上右边元素的积。
复杂度：时间复杂度O(n)，空间复杂度O(1)

js：

var productExceptSelf = function (nums) {    const res = [];    res[0] = 1;    //从左往右遍历    //记录从左到当前位置前一位的乘积    for (let i = 1; i < nums.length; i++) {        res[i] = res[i - 1] * nums[i - 1];    }
    let right = 1;    //从右往左遍历    //从左到当前位置前一位的乘积 乘上 右边元素的积    for (let j = nums.length - 1; j >= 0; j--) {        res[j] *= right;        right *= nums[j];    }
    return res;};

复制代码

java

class Solution {    public int[] productExceptSelf(int[] nums) {        int[] res = new int[nums.length];        res[0] = 1;        for (int i = 1; i < nums.length; i++) {            res[i] = res[i - 1] * nums[i - 1];
        }        int right = 1;        for (int i = nums.length - 1; i >= 0; i--) {
            res[i] *= right;            right *= nums[i];        }        return res;    }}

复制代码

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

方法 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};

复制代码

java：

class Solution {    public int[] sortArrayByParity(int[] A) {        int i = 0, j = A.length - 1;        while (i < j) {            if (A[i] % 2 > A[j] % 2) {                int tmp = A[i];                A[i] = A[j];                A[j] = tmp;            }
            if (A[i] % 2 == 0) i++;            if (A[j] % 2 == 1) j--;        }
        return A;    }}

复制代码

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

方法 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;};

复制代码

java：

class Solution {    public int[] sortArrayByParityII(int[] nums) {        int n = nums.length;        int j = 1;        for (int i = 0; i < n; i += 2) {            if (nums[i] % 2 == 1) {                while (nums[j] % 2 == 1) {                    j += 2;                }                swap(nums, i, j);            }        }           return nums;    }
    public void swap(int[] nums, int i, int j) {        int temp = nums[i];        nums[i] = nums[j];        nums[j] = temp;    }}

复制代码

发布于: 4 小时前阅读数: 6

全栈潇晨

关注

还未添加个人签名 2021.02.17 加入

还未添加个人简介

发布

暂无评论

创作场景

大厂算法面试之 leetcode 精讲 19. 数组

搞定大厂算法面试之 leetcode 精讲 19.数组

视频讲解（高效学习）:点击学习

目录：

数组操作的时间复杂度

283. 移动零 (easy)

方法 1:两次遍历

方法 2:双指针一次遍历

75. 颜色分类（medium）

方法 1.双指针

方法 2.双指针

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

方法 1:二分法

方法 2:双指针

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

方法 1:滑动窗口

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

方法 1：集合

方法 2：排序+双指针

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

方法 1:哈希表

方法 2:双指针

27. 移除元素 (easy)

217. 存在重复元素（easy）

方法 1.排序

方法 2.哈希表

238. 除自身以外数组的乘积 (medium)

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

方法 1.排序

方法 2.双指针

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

方法 1.双指针

全栈潇晨

评论

创作场景

大厂算法面试之 leetcode 精讲 19. 数组

搞定大厂算法面试之 leetcode 精讲 19.数组

视频讲解（高效学习）:点击学习

目录：

数组操作的时间复杂度

283. 移动零 (easy)

方法 1:两次遍历

方法 2:双指针一次遍历

75. 颜色分类 （medium）

方法 1.双指针

方法 2.双指针

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

方法 1:二分法

方法 2:双指针

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

方法 1:滑动窗口

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

方法 1：集合

方法 2：排序+双指针

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

方法 1:哈希表

方法 2:双指针

27. 移除元素 (easy)

217. 存在重复元素 （easy）

方法 1.排序

方法 2.哈希表

238. 除自身以外数组的乘积 (medium)

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

方法 1.排序

方法 2.双指针

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

方法 1.双指针

全栈潇晨

评论

75. 颜色分类（medium）

217. 存在重复元素（easy）