调整数组顺序使奇数位于偶数前面
# 📃 题目描述
题目链接:剑指 Offer 21. 调整数组顺序使奇数位于偶数前面 (opens new window)
# 🔔 解题思路
# 双指针(不稳定)
和 283. 移动零 - 力扣(LeetCode) (leetcode-cn.com) (opens new window) 一样,left 指针指向偶数,right 用来找奇数,然后将两个指针指向的元素进行交换就可以,这种方法没法保证原始顺序,是一种不稳定的算法
class Solution {
public int[] exchange(int[] nums) {
int left = 0;
int right = left + 1;
while (left < nums.length) {
// 当前数是偶数,向后找到第一个奇数与其交换
if (nums[left] % 2 == 0) {
right = left + 1;
for (; right < nums.length; right ++) {
if (nums[right] % 2 != 0) {
swap(nums, left, right);
break;
}
}
}
left ++;
}
return nums;
}
private void swap(int[] nums, int left, int right) {
int temp = nums[left];
nums[left] = nums[right];
nums[right] = temp;
}
}
# 冒泡(稳定)
类似于冒泡排序的思想,从后往前两两比较,如果发现偶数在前而奇数在后,则进行交换,就是相当于把奇数不断的冒泡到数组的前面
稳定的算法,但是时间复杂度 O(N^2),LC 上这道题会超时
秋招做天翼云笔试的时候有这个原题,要求保证相对顺序,这样做能 AC
class Solution {
public int[] exchange(int[] nums) {
int n = nums.length;
for (int i = 0; i < n - 1; i ++) {
for (int j = n - 1; j > 0; j --) {
int pre = nums[j - 1];
int post = nums[j];
// 偶数在前,奇数在后,则进行交换
if (pre % 2 == 0 && post % 2 != 0) {
swap(nums, j - 1, j);
}
}
}
return nums;
}
private void swap(int[] nums, int left, int right) {
int temp = nums[left];
nums[left] = nums[right];
nums[right] = temp;
}
}
🎁 公众号

各位小伙伴大家好呀,叫我小牛肉就行,目前在读东南大学硕士,上方扫码关注公众号「飞天小牛肉」,与你分享我的成长历程与技术感悟~
帮助小牛肉改善此页面 (opens new window)
Last Updated: 2023/02/16, 11:27:10