Sort Array By Parity LT905
2024-09-01 11:18:29
Given an array A of non-negative integers, return an array consisting of all the even elements of A, followed by all the odd elements of A.
You may return any answer array that satisfies this condition.
Example 1:
Input: [3,1,2,4]
Output: [2,4,3,1]
The outputs [4,2,3,1], [2,4,1,3], and [4,2,1,3] would also be accepted.
Note:
1 <= A.length <= 50000 <= A[i] <= 5000
Idea 1. Borrow the partition idea from quicksort, like Dutch flag problem, assume the array is already sorted as required, what to do with new element?
even | odd | ?
Time complexity: O(n)
Space complexity: O(1)
class Solution {
private void swap(int[] A, int i, int j) {
int a = A[i];
A[i] = A[j];
A[j] = a;
}
public int[] sortArrayByParity(int[] A) {
int evenEnd = -1;
for(int i = 0; i < A.length; ++i) {
if(A[i]%2 == 0) {
++evenEnd;
swap(A, evenEnd, i);
}
}
return A;
}
}
Idea 1.a Two pointers walking toward each other and swap if not in the right place
class Solution {
private void swap(int[] A, int i, int j) {
int a = A[i];
A[i] = A[j];
A[j] = a;
}
public int[] sortArrayByParity(int[] A) {
for(int left = 0, right = A.length-1; left < right; ) {
while(left < right && A[left]%2 == 0) {
++left;
}
while(left < right && A[right]%2 == 1) {
--right;
}
if(left < right) {
swap(A, left, right);
++left;
--right;
}
}
return A;
}
}
slightly more cleaner
class Solution {
private void swap(int[] A, int i, int j) {
int a = A[i];
A[i] = A[j];
A[j] = a;
}
public int[] sortArrayByParity(int[] A) {
for(int left = 0, right = A.length-1; left < right; ) {
if(A[left]%2 == 1 && A[right]%2 == 0) {
swap(A, left, right);
}
if(A[left]%2 == 0) {
++left;
}
if(A[right]%2 == 1) {
--right;
}
}
return A;
}
}
Idea 2. customised comparator to sort
Time complexity: O(nlogn)
Space complexity: O(n)
class Solution {
public int[] sortArrayByParity(int[] A) {
Integer[] B = new Integer[A.length];
for(int i = 0; i < A.length; ++i) {
B[i] = A[i];
}
Comparator<Integer> cmp = (a, b) -> Integer.compare(a%2, b%2);
Arrays.sort(B, cmp);
for(int i = 0; i < A.length; ++i) {
A[i] = B[i];
}
return A;
}
}
最新文章
- CentOS6.7安装RabbitMQ3.6.5
- Oracle_RAC数据库GI的PSU升级(11.2.0.4.0到11.2.0.4.8)
- 编译nginx时，编译参数注意点
- javascript中的原始值和复杂值
- Mac/Linux 定时运行命令行
- (05)odoo数据库和业务操作
- 完全卸载Oracle方法
- mysql违背了唯一约束
- Fun with layers
- Ubuntu 14.10安装SecureCRT 7.3
- 【UVALive - 3487】 Duopoly（网络流-最小割）
- SPL的基本使用
- Nutch 二次开发parse纸
- 扩展jquery easyui datagrid编辑单元格
- [ios2] 关于CGBitmapContextCreate【转】
- ACboy needs your help again!
- macOS Sierra Version 10.12.6 环境下Tomcat的下载与安装以及InterlliJ IDEA 2017.2 环境下配置Tomcat 与创建Web项目
- 学习笔记-express路径问题
- Project facet Java version 1.8 not supported JDK版本不对无法启动项目解决办法
- springMVC集成CXF后调用已知的wsdl接口