TypeScript调整数组元素顺序算法

目录
  • 前言
  • 实现思路
  • 实现代码
    • 代码的可扩展性
  • 测试用例
  • 示例代码
  • 总结

前言

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

本文将带大家实现这个算法,欢迎各位感兴趣的开发者阅读本文。

实现思路

我们通过一个实例来分析下:假设有这样一个数组:[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<number>): 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<number>, 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);

示例代码

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

总结

到此这篇关于TypeScript调整数组元素顺序算法的文章就介绍到这了,更多相关ts调整数组元素顺序内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们!

时间: 2022-04-17

TypeScript函数和类型断言实例详解

目录 开始 断言 非空断言 类型断言 尖括号 as 确定赋值断言 类型守卫 trpeof in 函数 可选参数 默认值参数 函数重载 结束 开始 现在要加速学习了,大佬们有没有内推,给个推荐 会vue2/vue3 + ts 断言 非空断言 非空断言就是确定这个变量不是null或者undefined,就是把null或者undefined从他的类型中排除 function demo(message:string|undefined|null) { const str: string = messag

Typescript文件被识别为视频的问题解决

目录 概念引入 问题现象 解决办法 恢复视频模式 概念引入 TypeScript 是微软开发的一个开源的编程语言,通过在JavaScript的基础上添加静态类型定义构建而成 Transport Stream 即传输流,是一种常见的视频封装格式,基于MPEG-2的封装格式(所以也叫MPEG-TS) TypeScript和Transport Stream的文件扩展名均为ts 问题现象 在Windows操作系统上.ts被默认标记为Transport Stream,对于普通用户来讲这完全没有问题,但对于

TypeScript 使用 Tuple Union 声明函数重载

问题: TypeScript 中为函数添加多个签名后,依然需要添加相应的代码来判断并从不同的签名参数列表中获取对应的参数.过去常见的写法: function refEventEmitter(event?: string): void; function refEventEmitter(event: string, callback: () => void): void; function refEventEmitter(callback: () => void): void; function

如何在TypeScript中处理日期字符串

目录 前言: 一.模板字面量类型 二.类型谓词缩小范围 三.定义日期字符串 总结: 前言: 在我最近的一个项目中,我必须去处理多个自定义的日期字符串表示法,比如YYYY-MM-DD和YYYYMMDD.由于这些日期是字符串变量,TypeScript默认会推断成为string类型.虽然这在技术实现上没有错,但是在工作中使用这样的类型定义是很宽泛的,使得有效处理这些日期字符串变得很困难.例如,let dog = 'alfie'也被推断为一个string类型. 在这篇文章中,我会将我的解决方法呈现给你,

详解TypeScript使用及类型声明文件

目录 简介 Script 与 Vue3 defineProps 与 Typescript defineEmits 与 Typescript ref 与 Typescript computed 与 Typescript 事件对象 与 Typescript 模板 Ref 与 Typescript 可选链操作符 非空断言-TS TypeScript类型声明文件 基本介绍 内置类型声明文件 第三方库类型声明文件 自定义类型声明文件 简介 声明文件是以.d.ts为后缀的文件,开发者在声明文件中编写类型声明

详解TypeScript中的类型保护

概述 在 TypeScript 中使用联合类型时,往往会碰到这种尴尬的情况: interface Bird { // 独有方法 fly(); // 共有方法 layEggs(); } interface Fish { // 独有方法 swim(); // 共有方法 layEggs(); } function getSmallPet(): Fish | Bird { // ... } let pet = getSmallPet(); pet.layEggs(); // 正常 pet.swim();

详解TypeScript的基础类型

目录 布尔类型 数字类型 字符串类型 字符串和数字进行拼接 undefined和 null 数组类型 元组类型 枚举类型 any类型 void类型 联合类型 总结 布尔类型 // 布尔类型--->boolean // let 变量名:数据类型 = 值 let flag: boolean = true; console.log(flag) 数字类型 // 数字类型--->number let a1: number = 10 // 十进制 let a2: number = 0b1010 // 二进

详解TypeScript映射类型和更好的字面量类型推断

概述 TypeScript 2.1 引入了映射类型,这是对类型系统的一个强大的补充.本质上,映射类型允许w咱们通过映射属性类型从现有类型创建新类型.根据咱们指定的规则转换现有类型的每个属性.转换后的属性组成新的类型. 使用映射类型,可以捕获类型系统中类似Object.freeze()等方法的效果.冻结对象后,就不能再添加.更改或删除其中的属性.来看看如何在不使用映射类型的情况下在类型系统中对其进行编码: interface Point { x: number; y: number; } inte

详解 TypeScript 枚举类型

目录 1. 数字枚举 2. 字符串枚举 3. 反向映射 4. 异构枚举 5. 常量枚举 6. 枚举成员类型和联合枚举类型 (1)枚举成员类型 (2)联合枚举类型 7. 枚举合并 前言: TypeScript 在 ES 原有类型基础上加入枚举类型,使得在 TypeScript 中也可以给一组数值赋予名字,这样对开发者比较友好,可以理解枚举就是一个字典. 枚举类型使用enum来定义: enum Day { SUNDAY, MONDAY, TUESDAY, WEDNESDAY, THURSDAY, F

详解C 语言项目中.h文件和.c文件的关系

详解C 语言项目中.h文件和.c文件的关系 在编译器只认识.c(.cpp))文件,而不知道.h是何物的年代,那时的人们写了很多的.c(.cpp)文件,渐渐地,人们发现在很多.c(.cpp)文件中的声明语句就是相同的,但他们却不得不一个字一个字地重复地将这些内容敲入每个.c(.cpp)文件.但更为恐怖的是,当其中一个声明有变更时,就需要检查所有的.c(.cpp)文件. 于是人们将重复的部分提取出来,放在一个新文件里,然后在需要的.c(.cpp)文件中敲入#include XXXX这样的语句.这样即

详解Typescript里的This的使用方法

this可以说是Javascript里最难理解的特性之一了,Typescript里的 this 似乎更加复杂了,Typescript里的 this 有三中场景,不同的场景都有不同意思. this 参数: 限制调用函数时的 this 类型 this 类型: 用于支持链式调用,尤其支持 class 继承的链式调用 ThisType: 用于构造复杂的 factory 函数 this 参数 由于 javascript 支持灵活的函数调用方式,不同的调用场景,this 的指向也有所不同 作为对象的方法调用

详解TypeScript中type与interface的区别

目录 类型别名 type 接口 interface interface和type的相似之处 都可以描述 Object和Function Type Interface 二者都可以被继承 interface 继承 interface interface 继承 type type 继承 type type 继承 interface 实现 implements 二者区别 1. 定义基本类型别名 2. 声明联合类型 3. 声明元组 4. 声明合并 5. 索引签名问题 总结 类型别名 type 首先认识一下

详解配置 Apache 服务器支持 PHP 文件的解析

详解配置 Apache 服务器支持 PHP 文件的解析 [说明] 1. 本例中 Apache 版本为 httpd-2.4.20-x64-vc14 ,安装路径为 E:\Apache24 2. PHP 版本为 php-5.5.34-Win32-VC11-x64 ,安装路径为 E:\php-5.5.34 [下载] 登录 http://php.NET/downloads.php 下载 PHP,由于我要把它跟 Apache 集成,所以我这里下载的是 Thread Safe 版本: [安装] 1. 解压下载

详解Typescript 内置的模块导入兼容方式

一.前言 前端的模块化规范包括 commonJS.AMD.CMD 和 ES6.其中 AMD 和 CMD 可以说是过渡期的产物,目前较为常见的是commonJS 和 ES6.在 TS 中这两种模块化方案的混用,往往会出现一些意想不到的问题. 二.import * as 考虑到兼容性,我们一般会将代码编译为 es5 标准,于是 tsconfig.json 会有以下配置: { "compilerOptions": { "module": "commonjs&qu