「算法」按奇偶排序数组 & 按奇偶排序数组II

作者 : 开心源码 本文共1967个字,预计阅读时间需要5分钟 发布时间: 2022-05-13 共248人阅读

00905 按奇偶排序数组

题目形容

给定一个非负整数数组 A,返回一个数组,在该数组中 A 的所有偶数元素之后跟着所有奇数元素。

你可以返回满足此条件的任何数组作为答案。

示例:

输入:[3,1,2,4]输出:[2,4,3,1]输出 [4,2,3,1],[2,4,1,3] 和 [4,2,1,3] 也会被接受。 

提醒:

  • 1 <= A.length <= 5000
  • 0 <= A[i] <= 5000

力扣地址

  • https://leetcode.com/problems/sort-array-by-parity/
  • https://leetcode-cn.com/problems/sort-array-by-parity/

解题报告

两遍扫描

本题解由微信公众号小猿刷题提供, 错误之处, 欢迎指正.

第一遍扫描输出偶数, 第二遍扫描输出奇数.

/** * 微信公众号"小猿刷题" */class Solution {    public int[] sortArrayByParity(int[] A) {        int[] list = new int[A.length];        int t = 0;        for (int i = 0; i < A.length; i++) {             if (A[i] % 2 == 0){                 list[t++] = A[i];             }                        }        for (int i = 0; i < A.length; i++) {             if (A[i] % 2 == 1){                 list[t++] = A[i];             }                        }        return list;    }}

偶数交换

本题解由微信公众号小猿刷题提供, 错误之处, 欢迎指正.

遍历数组,将所有偶数元素依次交换到数组前列.

/** * 微信公众号"小猿刷题" */class Solution {    public static int[] sortArrayByParity(int[] A) {        int offset = 0;        for(int i = 0; i < A.length; i++){            if(A[i] % 2 == 0){                swap(A, i, offset++);            }        }        return A;    }        public static void swap(int[] arr, int left, int right){        int tmp = arr[left];        arr[left] = arr[right];        arr[right] = tmp;    } }

原地快排

本题解由微信公众号小猿刷题提供, 错误之处, 欢迎指正.

  • 定义两个指针分别从高位(寻觅偶数元素)和低位(寻觅奇数元素)扫描. 寻觅到交换位置.
/** * 微信公众号"小猿刷题" */class Solution {        public static int[] sortArrayByParity(int[] A) {        int left = 0;        int right = A.length - 1;        while(left < right){            // 遍历直到第一个偶数跳出            while(left < right && A[right] % 2 != 0){                right --;            }            // 遍历直到第一个奇数跳出            while(left < right && A[left] % 2 == 0){                left ++;            }            swap(A, left, right);        }        return A;    }        public static void swap(int[] arr, int left, int right){        int tmp = arr[left];        arr[left] = arr[right];        arr[right] = tmp;    } }

小猿刷题

00922 按奇偶排序数组 II

题目形容

给定一个非负整数数组 A, A 中一半整数是奇数,一半整数是偶数。对数组进行排序,以便当 A[i] 为奇数时,i 也是奇数;当 A[i] 为偶数时, i 也是偶数。

你可以返回任何满足上述条件的数组作为答案。

示例:

输入:[4,2,5,7]输出:[4,5,2,7]解释:[4,7,2,5],[2,5,4,7],[2,7,4,5] 也会被接受。

提醒:

  • 2 <= A.length <= 20000
  • A.length % 2 == 0
  • 0 <= A[i] <= 1000

力扣地址

  • https://leetcode.com/problems/sort-array-by-parity-ii/
  • https://leetcode-cn.com/problems/sort-array-by-parity-ii/

解题报告

本题解由微信公众号小猿刷题提供, 错误之处, 欢迎指正.

  • 定义两个指针,分别记录偶数和奇数元素的位置.
  • 遍历数组把所有的偶数放进 ans[0],ans[2],ans[4],奇数放进 ans[1],ans[3],ans[5],依次类推.
/** * 微信公众号"小猿刷题" */class Solution {    public int[] sortArrayByParityII(int[] A) {        int[] list = new int[A.length];        int i = 0;        int j = 1;        for (int x: A) {            if (x % 2 == 0) {                list[i] = x;                i += 2;            }            if (x % 2 == 1) {                list[j] = x;                j += 2;            }        }        return list;    }}

小猿刷题

说明
1. 本站所有资源来源于用户上传和网络,如有侵权请邮件联系站长!
2. 分享目的仅供大家学习和交流,您必须在下载后24小时内删除!
3. 不得使用于非法商业用途,不得违反国家法律。否则后果自负!
4. 本站提供的源码、模板、插件等等其他资源,都不包含技术服务请大家谅解!
5. 如有链接无法下载、失效或广告,请联系管理员处理!
6. 本站资源售价只是摆设,本站源码仅提供给会员学习使用!
7. 如遇到加密压缩包,请使用360解压,如遇到无法解压的请联系管理员
开心源码网 » 「算法」按奇偶排序数组 & 按奇偶排序数组II

发表回复