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