题目地址(21. 调整数组顺序使奇数位于偶数前面)

https://leetcode-cn.com/problems/diao-zheng-shu-zu-shun-xu-shi-qi-shu-wei-yu-ou-shu-qian-mian-lcof/

题目描述

  1. 输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有奇数在数组的前半部分，所有偶数在数组的后半部分。
  5. 示例：
  7. 输入：nums = [1,2,3,4]
  8. 输出：[1,3,2,4] 
  9. 注：[3,1,2,4] 也是正确的答案之一。
  13. 提示：
  15. 0 <= nums.length <= 50000
  16. 0 <= nums[i] <= 10000

前置知识


公司

  • 暂无

思路

考虑定义双指针 ii , jj 分列数组左右两端，循环执行：

  1. 指针 ii 从左向右寻找偶数；
  2. 指针 jj 从右向左寻找奇数；
  3. 将 偶数 nums[i]nums[i] 和 奇数 nums[j]nums[j] 交换。

可始终保证： 指针 ii 左边都是奇数，指针 jj 右边都是偶数 。
image.png

关键点


代码

  • 语言支持：Java

Java Code:

  2. class Solution {
  3.     public int[] exchange(int[] nums) {
  4.         int i = 0, j = nums.length - 1, tmp;
  5.         while(i < j) {
  6.             //这里注意也要判断i<j
  7.             while(i < j && (nums[i] & 1) == 1) i++;
  8.             while(i < j && (nums[j] & 1) == 0) j--;
  9.             tmp = nums[i];
  10.             nums[i] = nums[j];
  11.             nums[j] = tmp;
  12.         }
  13.         return nums;
  14.     }
  15. }

复杂度分析

令 n 为数组长度。

  • 时间复杂度：剑指 Offer 21. 调整数组顺序使奇数位于偶数前面 - 图2#card=math&code=O%28n%29&id=crp6q)
  • 空间复杂度：剑指 Offer 21. 调整数组顺序使奇数位于偶数前面 - 图3#card=math&code=O%28n%29&id=U2vu5)