写点什么

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

作者:全栈潇晨
  • 2021 年 12 月 04 日
  • 本文字数:12360 字

    阅读完需:约 41 分钟

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

视频讲解(高效学习):点击学习

目录:

1.开篇介绍


2.时间空间复杂度


3.动态规划


4.贪心


5.二分查找


6.深度优先&广度优先


7.双指针


8.滑动窗口


9.位运算


10.递归&分治


11剪枝&回溯


12.堆


13.单调栈


14.排序算法


15.链表


16.set&map


17.栈


18.队列


19.数组


20.字符串


21.树


22.字典树


23.并查集


24.其他类型题

数组操作的时间复杂度

  • 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; }}
复制代码


用户头像

全栈潇晨

关注

还未添加个人签名 2021.02.17 加入

还未添加个人简介

评论

发布
暂无评论
大厂算法面试之leetcode精讲19.数组