Loading...
墨滴

CYF

2021/04/26  阅读:67  主题:默认主题

# 调整数组顺序使奇数位于偶数前面

img
img

来源:力扣(LeetCode)

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

示例:

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

这个题可以有三个思路:

  1. 借助新数组
  2. 首尾双指针
  3. 快慢双指针

方法一:借助新数组

  • 新建一个新数组,把奇数从新数组的前面存进去(unshift ),把偶数从新数组的后面存进去(push
  • 或者借助两个数组,把奇数存到一个数组中,把偶数存到另外一个数组中,将两个数组相加
var exchange = function(nums{
    let newArr = []
    nums.forEach(function(value, index{
        if (value % 2 !==0) {
            newArr.unshift(value)
        } else {
            newArr.push(value)
        }
    })
    return newArr
};
  • 时间复杂度为:O(n)
  • 空间复杂度为:O(n)
img
img

方式二:首尾双指针

  • 定义一个指针指向首位,另一个指针指向尾部
  • 首指针往后走,若是奇数就一直往后走,偶数就停下来
  • 尾指针往前走,若是偶数数就一直往前走,奇数就停下来
  • 两个指针指向的数进行交换
  • 两指针继续移动,直到首指针left > 尾指针right
img
img
var exchange = function(nums{
    let left = 0;
    let right = nums.length - 1;
    while (left <= right) {
        // 首指针,找出偶数
        while (left <= right && nums[left] % 2 !== 0) {
            left++
        }
        // 尾指针,找出奇数
        while (left <= right && nums[right] % 2 === 0) {
            right--
        }
        if (left > right) {
            break
        }
        [nums[left], nums[right]] = [ nums[right], nums[left]]
        left++;
        right--;
        
    }
    return nums
};
  • 时间复杂度为:O(n)
  • 空间复杂度为:O(1)
img
img

方法三:快慢双指针

  • 快慢指针刚开始都指向第一个
  • 由快指针走在最前面来发现奇数,慢指针负责指向第一个偶数
  • 如果快指针发现奇数,立即与慢指针交换
  • 快指针移到下一个数进行判断,慢指针则移动到下一个偶数
img
img
var exchange = function(nums{
    let slow = 0, fast = 0;
    let n = nums.length - 1
    while (fast <= n) {
        if (nums[fast] % 2 === 1) {
            [nums[slow], nums[fast]] = [nums[fast], nums[slow]]
            slow++;
        }
        fast++;
    }
    return nums
};
  • 时间复杂度为:O(n)
  • 空间复杂度为:O(1)
img
img

CYF

2021/04/26  阅读:67  主题:默认主题

作者介绍

CYF