当前位置：首页 > 科技 > 知识百科

调整数组元素顺序，你了解几分？

来源：责编：时间：2023-08-07 16:30:11 167观看

导读前言有一个整数数组，我们想按照特定规则对数组中的元素进行排序，比如：数组中的所有奇数位于数组的前半部分。实现思路我们通过一个实例来分析下：假设有这样一个数组：[2, 4, 5, 6,

前言

有一个整数数组，我们想按照特定规则对数组中的元素进行排序，比如：数组中的所有奇数位于数组的前半部分。

实现思路

我们通过一个实例来分析下：假设有这样一个数组：[2, 4, 5, 6, 7, 8, 9, 11]，将奇数移动到最前面后，就是：[11, 9, 5, 7, 6, 8, 4, 2]。

通过观察后，我们发现在扫描这个数组的时候，如果发现有偶数出现在奇数的前面，就交换他们的顺序，交换之后就符合要求了。

因此，我们可以维护两个指针：

第一个指针初始化时指向数组的第一个数字，它只向后移动;第二个指针初始化时指向数组的最后一个数字，它只向前移动;

在两个指针相遇之前，第一个指针总是位于第二个指针的前面。如果第一个指针指向的数字是偶数，并且第二个指针指向的数字是奇数，则交换这两个数字。

接下来，我们来通过图来描述下上述例子交换指针的过程，如下所示：

第一个指针永远指向偶数，如果不为偶数就向后移动;第二个指针永远指向奇数，如果不为奇数就向前移动;当两个指针各自指向的数都符合条件时，就交换两个元素的位置;交换完成后，重复上述步骤，直至两个指针相遇或者第一个指针位于第二个指针之后则代表问题已得到解决。

实现代码

有了思路之后，我们来看下实现代码，如下所示：

export class AdjustArrayOrder {
// 指向数组元素的两个指针：一个指向数组头部、一个指向数组尾部
private begin = 0;
private end = 0;

// 调整数组中奇数与偶数元素的位置：奇数位于偶数前面
reorderOddEven(arr: Array): void {
this.end = arr.length - 1;
while (this.begin < this.end) {
// 向后移动begin(转成二进制跟1做与运算，运算结果为0就表示为偶数)，直至其指向偶数
while (this.begin < this.end && (arr[this.begin] & 0x1) !== 0) {
this.begin++;
}

// 向前移动end（转成二进制跟1做与运算，运算结果为1就表示为奇数），直至其指向奇数
while (this.begin < this.end && (arr[this.end] & 0x1) === 0) {
this.end--;
}

// begin指向了偶数，end指向了奇数
if (this.begin < this.end) {
// 交换两个元素的顺序
[arr[this.begin], arr[this.end]] = [arr[this.end], arr[this.begin]];
}
}
// 重置指针位置
this.begin = 0;
this.end = 0;
}
}代码的可扩展

性如果数组中的元素不按照奇前偶后排列，我们需要将其按照大小进行划分，所有负数都排在非负数的前面，应该怎么做?

聪明的开发者可能已经想到了方案：双指针的思路还是不变，我们只需修改内层while循环的的判断条件即可。

这样回答没有问题，确实解决了这个问题，那么如果再改改题目，我们需要把数组中的元素分为两部分，能被3整除的数都在不能被3整除的数前面，应该怎么做?

经过思考后，我们发现这个问题无论再怎么改变都有一个共同的部分：双指针的逻辑永远不会变。变化的只是判断条件，那么我们就可以把变化的部分提取成函数，当作参数让调用者传进来，这样就完美的解决了这个问题，也正是我们所提及的代码的可扩展性。

最后，我们来看下实现代码，如下所示：

// 元素排序
reorder(arr: Array, checkFun: (checkVal: number) => boolean): void {
this.end = arr.length - 1;
while (this.begin < this.end) {
// 向后移动begin
while (this.begin < this.end && !checkFun(arr[this.begin])) {
this.begin++;
}

// 向前移动end
while (this.begin < this.end && checkFun(arr[this.end])) {
this.end--;
}

// begin与end都指向了正确的位置
if (this.begin < this.end) {
// 交换两个元素的顺序
[arr[this.begin], arr[this.end]] = [arr[this.end], arr[this.begin]];
}
}测试用例

我们先来测试下奇数在偶数之前的函数处理代码能否正常执行，如下所示：

const adjustArrayOrder = new AdjustArrayOrder();
// 奇数在前
const arr = [2, 4, 5, 6, 7, 8, 9, 11];
adjustArrayOrder.reorderOddEven(arr);
console.log(arr);

执行结果如下所示：

最后，我们来测试下reorder函数能否正常执行：

负数在数组的最前面// 负数在前
const checkMinusNumber = function (val: number) {
return val > 0;
};
const arr = [2, 4, 5, 6, 7, -8, -10 - 12, -2];
adjustArrayOrder.reorder(arr, checkMinusNumber);
console.log(arr);

能被3整除的数在数组的最前面const checkDivisible = function (val: number) {
return val % 3 !== 0;
};
const arr = [2, 4, 5, 6, 3, 6, 9, 12];
adjustArrayOrder.reorder(arr, checkDivisible);
console.log(arr);

示例代码

文中所举代码的完整版请移步：

AdjustArrayOrder.ts[1]adjustArrayOrder-test.ts[2]参考资料

[1]AdjustArrayOrder.ts: https://github.com/likaia/algorithm-practice/blob/e7f6a38021426397af60a73d4c6b8bf88548ba91/src/AdjustArrayOrder.ts#L2

[2]adjustArrayOrder-test.ts: https://github.com/likaia/algorithm-practice/blob/e7f6a38021426397af60a73d4c6b8bf88548ba91/src/test-case/adjustArrayOrder-test.ts#L3

[3]个人网站: https://www.kaisir.cn/

本文链接：http://www.28at.com/showinfo-119-2283-0.html调整数组元素顺序，你了解几分？

声明：本网页内容旨在传播知识，若有侵权等问题请及时与本网联系，我们将在第一时间删除处理。邮件：2376512515@qq.com

上一篇：数据分析和数据科学的五大不同之处译文

下一篇：亚马逊云计算主管：AWS将保持云服务领先地位不打算将其分拆

标签：

热门焦点

iPhone卖不动了！苹果股价创年内最大日跌幅：市值一夜蒸发万亿元

8月5日消息，今天凌晨美股三大指数高开低走集体收跌，道指跌0.41%；纳指跌0.36%；标普500指数跌0.52%。热门科技股也都变化极大，其中苹果报181.99美元，跌4.8%，创
Rust中的高吞吐量流处理

作者 | Noz编译 | 王瑞平本篇文章主要介绍了Rust中流处理的概念、方法和优化。作者不仅介绍了流处理的基本概念以及Rust中常用的流处理库，还使用这些库实现了一个流处理程序
一年经验在二线城市面试后端的经验分享

忠告这篇文章只适合2年内工作经验、甚至没有工作经验的朋友阅读。如果你是2年以上工作经验，请果断划走，对你没啥帮助~主人公这篇文章内容来自「升职加薪」星球星友的投稿，坐
不容错过的MSBuild技巧，必备用法详解和实践指南

一、MSBuild简介MSBuild是一种基于XML的构建引擎，用于在.NET Framework和.NET Core应用程序中自动化构建过程。它是Visual Studio的构建引擎，可在命令行或其他构建工具中使用
.NET 程序的 GDI 句柄泄露的再反思

一、背景1. 讲故事上个月我写过一篇如何洞察 C# 程序的 GDI 句柄泄露文章，当时用的是 GDIView + WinDbg 把问题搞定，前者用来定位泄露资源，后者用来定位泄露代码，后面有朋友反
小红书1周涨粉49W+，我总结了小白可以用的N条涨粉笔记

作者：黄河懂运营一条性教育视频，被54万人“珍藏”是什么体验？最近，情感博主@公主是用鲜花做的，火了！仅仅凭借一条视频，光小红书就有超过128万人，为她疯狂点赞！更疯狂的是，这
大厂卷向扁平化

来源：新熵作者丨南枝编辑丨月见大厂职级不香了。俗话说，兵无常势，水无常形，互联网企业调整职级体系并不稀奇。7月13日，淘宝天猫集团启动了近年来最大的人力制度改革，目前已形成一
机构称Q2国内智能手机销量同比下滑4% vivo份额重回第1

7月29日消息，根据市场调查机构Counterpoint Research公布的最新报告，2023年第2季度中国智能手机销量同比下降4%，创新自2014年以来第2季度销量新低。报
OPPO K11评测：旗舰级IMX890加持 2000元档最强影像手机

【Techweb评测】中端机型用户群体巨大，占了中国目前手机市场的大头，一直以来都是各手机品牌的“必争之地”，其中OPPO K系列机型一直以来都以高品质、