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

原创

全栈潇晨

发布于 2021-12-04 07:21:59

3940

发布于 2021-12-04 07:21:59

文章被收录于专栏：高级前端工程师学习必备高级前端工程师学习必备

搞定大厂算法面试之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. 遇见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++
        }
    }
};

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
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++;
        }
    }
};

//写法2
var 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;
            }
        }
    }
}

//写法2
public 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的时候循环数组
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;
};

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

原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。

如有侵权，请联系 cloudcommunity@tencent.com 删除。

腾讯广告算法大赛

原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。

如有侵权，请联系 cloudcommunity@tencent.com 删除。

腾讯广告算法大赛

登录后参与评论

0 条评论

热度

搞定大厂算法面试之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）