输入一个长度为 n 整数数组，数组里面可能含有相同的元素，实现一个函数来调整该数组中数字的顺序，使得所有的奇数位于数组的前面部分，所有的偶数位于数组的后面部分，对奇数和奇数，偶数和偶数之间的相对位置不做要求，但是时间复杂度和空间复杂度必须如下要求。
数据范围：
，数组中每个数的值 
要求：时间复杂度 )
，空间复杂度 )
[编程题]调整数组顺序使奇数位于偶数前面(二)
利用list的有序性，分别把奇数和偶数放在两个list中，然后合并两个list，在通过stream流把list转为int数组
import java.util.*;
public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param array int整型一维数组
* @return int整型一维数组
*/
public int[] reOrderArrayTwo (int[] array) {
// write code here
List<Integer> list1=new ArrayList<>();
List<Integer> list2=new ArrayList<>();
for(int a:array){
if(a%2!=0){
list1.add(a);
}else{
list2.add(a);
}
}
list1.addAll(list2);
return list1.stream().mapToInt(Integer::intValue).toArray();
}
}
发表于 2023-11-22 17:40:11
回复(0)
双指针法的使用，无需辅助控空间！
一次循环
import java.util.*;
public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param array int整型一维数组
* @return int整型一维数组
*/
public int[] reOrderArrayTwo (int[] array) {
if(array.length<=1)return array;
// write code here
int left = 0;
int right = 1;
while(right<array.length){
if(array[left]%2==1){
left++;
right++;
}else if(array[left]%2==0 && array[right]%2==1){
int temp = array[right];
array[right]=array[left];
array[left]=temp;
left++;
right++;
}else{
right++;
}
}
return array;
}
}
发表于 2022-11-25 16:38:37
回复(0)
双指针法
public int[] reOrderArrayTwo(int[] array) {
int l = 0, r = array.length - 1, tmp = 0;
// 终止条件：左右指针相遇
while (l < r) {
if ((array[l] & 1) == 1) {
// 奇数：左指针往右挪
l++;
} else {
// 偶数：交换后，右指针往左挪
tmp = array[l];
array[l] = array[r];
array[r] = tmp;
r--;
}
}
return array;
}
发表于 2022-08-16 20:24:49
回复(0)
调整数组顺序使奇数位于偶数前面
保证奇数与奇数，偶数与偶数的相对位置时，声明数组遍历两遍，时间O(n)，空间O(n)
不保证相对位置，双指针找，时间O(n)，空间O(1)，虽然里面嵌套while，但是只遍历一遍
import java.util.*;
public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param array int整型一维数组
* @return int整型一维数组
*/
public int[] reOrderArrayTwo (int[] array) {
// write code here
//虽然里面是嵌套的while，但是只遍历一遍，所以时间复杂度O(n)
//不保证奇数与奇数，偶数与偶数的相对位置，时间复杂度O(n)，空间复杂度O(1)
int s = 0, e = array.length-1;
while(s < e){
while(s < array.length && (array[s] & 1) != 0) s++;
while(e >= 0 && (array[e] & 1) != 1) e--;
if(s < e){
int temp = array[s];
array[s] = array[e];
array[e] = temp;
}
}
return array;
}
}
发表于 2022-07-30 20:40:56
回复(0)
import java.util.*;
public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param array int整型一维数组
* @return int整型一维数组
*/
public int[] reOrderArrayTwo (int[] array) {
// write code here
int right = array.length;
int index = 0;
while(index < right){
if(array[index] % 2 == 0){
right--;
swap(array, index, right);
} else{
index++;
}
}
return array;
}
public static void swap(int[] arr, int a, int b){
int temp = arr[a];
arr[a] = arr[b];
arr[b] = temp;
}
}
发表于 2022-07-17 13:01:07
回复(0)
快排思想
import java.util.*;
public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param array int整型一维数组
* @return int整型一维数组
*/
public int[] reOrderArrayTwo (int[] array) {
// write code here
int p=0;
int q=array.length-1;
//快排
while(p<q){
//看右边
while(p<q&&array[q]%2==0){
q--;
}
while(p<q&&array[p]%2==1){
p++;
}
swap(array,q,p);
}
return array;
}
public void swap(int[] arr,int val1,int val2){
int temp=arr[val1];
arr[val1]=arr[val2];
arr[val2]=temp;
}
}
public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param array int整型一维数组
* @return int整型一维数组
*/
public int[] reOrderArrayTwo (int[] array) {
// write code here
int p=0;
int q=array.length-1;
//快排
while(p<q){
//看右边
while(p<q&&array[q]%2==0){
q--;
}
while(p<q&&array[p]%2==1){
p++;
}
swap(array,q,p);
}
return array;
}
public void swap(int[] arr,int val1,int val2){
int temp=arr[val1];
arr[val1]=arr[val2];
arr[val2]=temp;
}
}
发表于 2022-07-09 23:18:35
回复(0)
import java.util.*;
public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param array int整型一维数组
* @return int整型一维数组
*/
public int[] reOrderArrayTwo(int[] array) {
// write code here
// 奇数指针，从前往后遍历
int low = 0;
//偶数指针，从后往前遍历
int high = array.length - 1;
int temp = 0;
while (low < high) {
//左右都是奇数，左移右不动
if (array[low] % 2 == 1 && array[high] % 2 == 1) {
low++;
}
// 左奇数，右偶数
else if (array[low] % 2 == 1 && array[high] % 2 == 0) {
low++;
high--;
}
// 左偶数，右奇数,交换位置
else if (array[low] % 2 == 0 && array[high] % 2 == 1) {
temp = array[low];
array[low] = array[high];
array[high] = temp;
}
// 左右都是偶数
else {
high--;
}
}
return array;
}
}
发表于 2022-04-23 10:43:06
回复(0)
import java.util.*;
public class Solution {
public int[] reOrderArrayTwo (int[] array) {
int l = 0;
int r = array.length-1;
while(l<=r){
if(array[l]%2==0){
if(array[r]%2!=0){
//左边是偶数，右边是奇数，对调
int temp = array[l];
array[l] = array[r];
array[r] = temp;
l++;
r--;
}else
//左边是偶数，右边是偶数，右边往前推，直到为奇数为止
r--;
}else
//左边是奇数，符合要求，继续往后看
l++;
}
return array;
}
}
发表于 2022-04-07 19:58:20
回复(0)
public int[] reOrderArrayTwo (int[] array) {
// write code here
int i=0;
int j=array.length-1;
while(i<j){
while(i<j&&((array[j]&1)==0)) j--;
while(i<j&&((array[i]&1)==1)) i++;
int temp=array[i]^array[j];
array[i]=temp^array[i];
array[j]=temp^array[j];
}
return array;
}
发表于 2022-04-06 16:49:20
回复(0)
import java.util.*;
public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param array int整型一维数组
* @return int整型一维数组
*/
public int[] reOrderArrayTwo (int[] array) {
int left=0,right = array.length-1;
while(left < right){
while( left<right && (array[left]&1)==1 ){
left++;
}
while(right>left && (array[right]&1)==0 ){
right--;
}
swap(array,left,right);
}
return array;
}
private void swap(int[] array,int i,int j){
int temp = array[i];
array[i] = array[j];
array[j] = temp;
}
}
发表于 2022-02-25 15:17:14
回复(0)
import java.util.*;
public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param array int整型一维数组
* @return int整型一维数组
*/
public int[] reOrderArrayTwo (int[] array) {
// write code here
ArrayList<Integer> list = new ArrayList<>();
if (array.length == 1)
return array;
for (int i = 0; i < array.length; i++){
if (array[i]%2 == 1){
list.add(array[i]);
}
}
for (int i = 0; i < array.length; i++){
if (array[i]%2 == 0){
list.add(array[i]);
}
}
int[] res = new int[array.length];
for (int i=0;i<list.size();i++){
res[i] = list.get(i);
}
return res;
}
}
发表于 2021-12-15 22:42:34
回复(0)
import java.util.*;
public class Solution {
public int[] reOrderArrayTwo (int[] array) {
// array可能为空，或者只存在一个数字，这种情况下直接返回
if(array == null || array.length < 2)
return array;
// 使用双指针求解，l用来指示存放奇数的位置，r向后搜索奇数
// 如果r指示的数字是奇数，那么将r和l所指示的数字进行交换【所有的奇数放到前面，偶数在后面】
int l = 0, r = 0;
while(r < array.length){
if(pickToBefore(array[r]))
swap(array, l ++, r);
r ++;
}
return array;
}
// 交换 i 和 j 所对应的数字
private void swap(int[] num, int i, int j){
int tmp = num[i];
num[i] = num[j];
num[j] = tmp;
}
// 判断是否为奇数，如果是返回true；否则返回false
private boolean pickToBefore(int num){
return num % 2 != 0 ? true : false;
}
}
发表于 2021-11-28 18:32:35
回复(0)
public int[] reOrderArrayTwo (int[] array) {
// write code here
for(int i = 0, j = 0; i < array.length; i++) {
if(array[i] % 2 != 0) {
int temp = array[i];
array[i] = array[j];
array[j++] = temp;
}
}
return array;
}
发表于 2021-11-19 01:36:15
回复(3)
划分的思想，如果前面的数一直为奇数就++，如果后面的数一直为偶数就--，直到遇到了不满足的情况，前面的数为偶数，后面的数为奇数，就交换他们的位置。
import java.util.*;
public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param array int整型一维数组
* @return int整型一维数组
*/
public int[] reOrderArrayTwo (int[] array) {
// write code here
int low=0,high=array.length-1;
while(low<high){
while(low<high&&array[high]%2==0)
high--;
while (low<high&&array[low]%2==1)
low++;
int temp=array[low];
array[low]=array[high];
array[high]=temp;
low++;
high--;
}
return array;
}
}
发表于 2021-10-28 22:00:39
回复(0)
import java.util.*;
public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param array int整型一维数组
* @return int整型一维数组
*/
public int[] reOrderArrayTwo (int[] array) {
if(array.length==0||array.length==1){
return array;
}
int left=0;
int right=array.length-1;
while(left<right){
if(array[left]%2==0&&array[right]%2!=0){
int temp=array[left];
array[left]=array[right];
array[right]=temp;
left++;
right--;
}
if(array[left]%2!=0){
left++;
}
if(array[right]%2==0){
right--;
}
}
return array;
}
}
发表于 2021-10-14 20:33:17
回复(0)
问题信息
通过挑战的用户
查看代码-
2022-09-16 11:12:42
-
2022-09-16 10:07:00
-
2022-09-15 21:22:37
-
2022-09-15 20:23:56
-
2022-09-15 19:33:09
相关试题
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K2座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
