剑指offer - 调整数组顺序使奇数位于偶数前面 - JavaScript

题目描述: 输入一个整数数组,实现一个函数来调整该数组中数字的顺序,使得所有奇数位于数组的前半部分,所有偶数位于数组的后半部分。

题目分析

题目和示例都提示了,没要求“保持偶数和偶数之间的相对位置不变”。例如对 [1,2,3,4] 来说,[1,3,2,4][3,1,2,4] 都是正确答案。

解法 1:开辟新空间

此过程需要循环 2 次,时间复杂度 O(N), 空间复杂度 O(N)。过程如下:

  • 第一次循环依次找到偶数和奇数,并且将其分别存放到新开辟的空间中
  • 第二次循环将存放偶数和奇数的空间“连接”在一起

代码如下:

// ac地址:https://leetcode-cn.com/problems/diao-zheng-shu-zu-shun-xu-shi-qi-shu-wei-yu-ou-shu-qian-mian-lcof/
// 原文地址:https://xxoo521.com/2020-01-01-tiao-zheng-shu-zu/
/**
 * @param {number[]} nums
 * @return {number[]}
 */
var exchange = function(nums) {
    const arr = []; // 奇数数组
    const brr = []; // 偶数数组
    nums.forEach(item => {
        item % 2 ? arr.push(item) : brr.push(item);
    });

    return arr.concat(brr);
};

解法 2: 双指针交换

可以利用“双指针”,分别是指向数组头部的指针 i,与指向数组尾部的指针 j。过程如下:

  • i 向右移动,直到遇到偶数;j 向左移动,直到遇到奇数
  • 检查 i 是否小于 j,若小于,交换 i 和 j 的元素,回到上一步骤继续移动;否则结束循环

时间复杂度是 O(N),空间复杂度是 O(1)。代码如下:

// ac地址:https://leetcode-cn.com/problems/diao-zheng-shu-zu-shun-xu-shi-qi-shu-wei-yu-ou-shu-qian-mian-lcof/
// 原文地址:https://xxoo521.com/2020-01-01-tiao-zheng-shu-zu/
/**
 * @param {number[]} nums
 * @return {number[]}
 */
var exchange = function(nums) {
    const length = nums.length;
    if (!length) {
        return [];
    }

    let i = 0,
        j = length - 1;
    while (i < j) {
        while (i < length && nums[i] % 2) i++;
        while (j >= 0 && nums[j] % 2 === 0) j--;

        if (i < j) {
            [nums[i], nums[j]] = [nums[j], nums[i]];
            i++;
            j--;
        }
    }

    return nums;
};

拓展思考:基于插入排序思路

如果题目中的要求,加上“保证奇数和奇数,偶数和偶数之间的相对位置不变”这个条件,那么解法是什么呢?

这种思路和插入排序相似,时间复杂度 O(N^2),空间复杂度 O(1)。这里时间复杂度主要浪费在“保持偶数和奇数原相对位置不变”这个要求上。

整体的思路:

  • 指针 i 从 0 开始向右移动,如果遇到奇数,继续移动;遇到偶数,停下来,并进入循环
    • 设置新指针 j = i + 1,指针 j 向右移动,遇到偶数,继续移动;遇到奇数,停下来,并进入下一步
    • 将数组[i, j - 1] 的元素整体向右位移 1 位,然后将 j 上的元素赋给 i 上的元素
  • 检测是否遍历完成,未完成则回到第一步
// 原文地址:https://xxoo521.com/2020-01-01-tiao-zheng-shu-zu/
// ac地址:https://www.nowcoder.com/practice/beb5aa231adc45b2a5dcc5b62c93f593

/**
 * @param {number[]} array
 * @return {number[]}
 */
function reOrderArray(array) {
    const length = array.length;
    if (!length) {
        return [];
    }

    let i = 0;
    while (i < length) {
        if (array[i] % 2 === 0) {
            // 如果指针i对应的元素是偶数
            // 那么就需要找到其后出现的第一个奇数
            // 然后和指针i的元素进行交换
            let j = i + 1;
            for (; j < length && array[j] % 2 === 0; ++j) {}
            if (j === length) {
                break;
            } else {
                // 整体右移,保证原元素的相对位置不变
                const tmp = array[j];
                for (let k = j; k > i; k--) {
                    array[k] = array[k - 1];
                }
                array[i] = tmp;
            }
        }
        i++;
    }

    return array;
}

更多资料

评论

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×