提供了编程的基础技术教程

zl程序教程

您现在的位置是：首页 > 

当前栏目

剑指Offer题解 - Day27

题解 Offer
2023-06-13 09:11:15 时间

「剑指 Offer 21. 调整数组顺序使奇数位于偶数前面」

力扣题目链接[1]

输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有奇数在数组的前半部分，所有偶数在数组的后半部分。

「示例：」

输入：nums = [1,2,3,4]
输出：[1,3,2,4]
注：[3,1,2,4] 也是正确的答案之一。

「提示：」

  1. 0 <= nums.length <= 50000
  2. 0 <= nums[i] <= 10000

思路：

题目要求将奇数放在数组前面，将偶数放在数组后面，首先考虑使用暴力破解解题。

数组过滤

我们可以通过使用数组的filter方法分别过滤出数组中的奇数和偶数，然后拼接返回即可。

/**
 * @param {number[]} nums
 * @return {number[]}
 */
var exchange = function(nums) {
    let odd = nums.filter(item => item % 2 !== 0) // 过滤奇数
    let even = nums.filter(item => item % 2 === 0) // 过滤偶数
    return [...odd, ...even]; // 拼接返回新数组
};
  • 「时间复杂度 O(n)」。
  • 「空间复杂度 O(n)」。

分析：

通过数组方法进行过滤是一种比较直接的思路，但是无法达到本题考查的知识点的目的。调换数组内元素的位置，更合适的方法是采用双指针法，下面就来具体分析。

双指针

我们可以分别声明两个指针，分别指向数组的头部和尾部，当头部元素遇到偶数、尾部元素遇到奇数时，就调换两者指向的元素，然后指针分别后移和前移，重复进行判断。当两个指针相遇的时候，此时的数组元素就是奇数在前、偶数在后的格式。

/**
 * @param {number[]} nums
 * @return {number[]}
 */
var exchange = function(nums) {
    let left = 0; // 初始化左指针
    let right = nums.length - 1; // 初始化右指针
    while(left < right) { // 当两个指针相遇便终止循环
        if (nums[left] % 2 !== 0) { // 如果左指针就是奇数意味着不需要调换
            left++; // 左指针右移
            continue; // 进行下一次循环
        }
        if (nums[right] % 2 === 0) { // 与上面同理
            right--;
            continue;
        }
        [nums[right], nums[left]] = [nums[left], nums[right]] // 调换左右指针指向的数字
    }
    return nums; // 返回原地置换元素的数组
};
  • 「时间复杂度 O(n)」。
  • 「空间复杂度 O(1)」。

分析：

通过左右指针的方式进行奇偶判断，并原地调换元素。最终当指针相遇的时候，意味着已经调换完毕，最后的结果便是奇数在前，偶数在后。

复杂度方面，由于需要遍历整个数组，因此时间复杂度是O(n) ；维护了两个常量级别的指针，因此空间复杂度是O(1) 。

总结

通过双指针进行数组元素的原地置换，可以将空间复杂度由O(n)降低至O(1) ，因此优先使用双指针进行题解，不建议使用数组的方法进行题解，可以作为额外的思路进行了解。

参考资料

[1]力扣题目链接: https://leetcode-cn.com/leetbook/read/illustration-of-algorithm/5v8a6t/

相关文章