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调整数组元素顺序内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们!

(0)

相关推荐

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

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

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

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

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

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

  • TypeScript 使用 Tuple Union 声明函数重载

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

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

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

  • TypeScript调整数组元素顺序算法

    目录 前言 实现思路 实现代码 代码的可扩展性 测试用例 示例代码 总结 前言 有一个整数数组,我们想按照特定规则对数组中的元素进行排序,比如:数组中的所有奇数位于数组的前半部分. 本文将带大家实现这个算法,欢迎各位感兴趣的开发者阅读本文. 实现思路 我们通过一个实例来分析下:假设有这样一个数组:[2, 4, 5, 6, 7, 8, 9, 11],将奇数移动到最前面后,就是:[11, 9, 5, 7, 6, 8, 4, 2]. 通过观察后,我们发现在扫描这个数组的时候,如果发现有偶数出现在奇数的

  • Java算法实现调整数组顺序使奇数位于偶数之前的讲解

    调整数组顺序使奇数位于偶数之前 1. 题目描述 输入一个整数数组,实现一个函数来调整该数组中数字的顺序,使得所有的奇数位于数组的前半部分,所有的偶数位于位于数组的后半部分,并保证奇数和奇数,偶数和偶数之间的相对位置不变. 2. 题目分析 该题目类似于一个选择排序,将奇数选择出来,放置于数据前面的位置,保持其他未被选择的元素的相对位置不变: 1. 遍历数组,当数组元素为奇数是进行处理,判断条件为 n % 2 != 0 2. 设置一个变量标注当前已遍历的元素中奇数的个数oddNum,也是将该奇数元素

  • C语言算法练习之数组元素排序

    目录 一.问题描述 二.算法实例编译环境 三.算法实例实现过程 3.1.包含头文件 3.2.定义宏和声明数组 3.3.声明相关变量 3.4.随机生成十个数字赋值给数组 3.5.输出随机生成的十个数字 3.6.数组从小到大进行排序 3.7.输出数组元素排序好的数字 四.经典算法实例程序 完整代码 4.1.main.h文件 4.2.main.c文件 五.总结 一.问题描述 求数组的排序 问题的描述 如下几点所示 使用rand()库函数随机生成10个1-100之间的数字. 声明数组的大小为10. 随机

  • C语言找出数组中的特定元素的算法解析

    问题描述:一个int数组,里面数据无任何限制,要求求出所有这样的数a[i],其左边的数都小于等于它,右边的数都大于等于它.能否只用一个额外数组和少量其它空间实现.       思路:如果能用两个辅助数组,那么相对来说简单一点,可定义数组Min和数组Max,其中Min[i]表示自a[i]之后的最小值(包括a[i]),Max[i]表示自a[i]之前元素的最大值.有了这两个辅助数组后,对于a[i],如果它大于Max[i-1]并且小于Min[i+1],那么就符合要求.       但是题目要求是只用一个

  • TypeScript实现十大排序算法之冒泡排序示例详解

    目录 一. 冒泡排序的定义 二. 冒泡排序的流程 三. 冒泡排序的图解 四. 冒泡排序的代码 五. 冒泡排序的时间复杂度 六. 冒泡排序的总结 一. 冒泡排序的定义 冒泡排序是一种简单的排序方法. 基本思路是通过两两比较相邻的元素并交换它们的位置,从而使整个序列按照顺序排列. 该算法一趟排序后,最大值总是会移到数组最后面,那么接下来就不用再考虑这个最大值. 一直重复这样的操作,最终就可以得到排序完成的数组. 这种算法是稳定的,即相等元素的相对位置不会发生变化. 而且在最坏情况下,时间复杂度为O(

  • PHP 数组遍历顺序理解

    比如: <?php$arr['laruence'] = 'huixinchen';$arr['yahoo']    = 2007;$arr['baidu']    = 2008;foreach ($arr as $key => $val) {//结果是什么?} 又比如: <?php$arr[2] = 'huixinchen';$arr[1]  = 2007;$arr[0]  = 2008;foreach ($arr as $key => $val) {//现在结果又是什么?} 要完

  • 深入理解PHP之数组(遍历顺序) Laruence原创

    经常会有人问我, PHP的数组, 如果用foreach来访问, 遍历的顺序是固定的么? 以什么顺序遍历呢? 比如: 复制代码 代码如下: <?php $arr['laruence'] = 'huixinchen'; $arr['yahoo'] = 2007; $arr['baidu'] = 2008; foreach ($arr as $key => $val) { //结果是什么? } 又比如: 复制代码 代码如下: <?php $arr[2] = 'huixinchen'; $arr

  • javascript中数组的常用算法深入分析

    前言 Array是Javascript构成的一个重要的部分,它可以用来存储字符串.对象.函数.Number,它是非常强大的.因此深入了解Array是前端必修的功课.本文将给大家详细介绍了javascript中数组的常用算法,下面话不多说了,来一起看看详细的介绍吧 一.不改变原数组,返回新数组(字符串) 1.concat()   连接两个或者多个数组,两边的原始数组都不会变化,返回的是被连接数组的一个副本. 2.join()  把数组中所有的元素放入到一个字符串中,返回字符串 var a = [1

  • 原生JS实现列表子元素顺序反转的方法分析

    本文实例讲述了原生JS实现列表子元素顺序反转的方法.分享给大家供大家参考,具体如下: 编写一个函数将一个列表里面的所有子元素顺序反转,问题不难但是解决的方法却有多种,而且性能大不一样,下面就介绍几种常用的方法: 1. 采用直接的DOM操作: var ul = document.getElementById('target'); var list = ul.getElementByTagName('li'); var length = list.length; while(length--){ u

  • pandas调整列的顺序以及添加列的实现

    在对excel的操作中,调整列的顺序以及添加一些列也是经常用到的,下面我们用pandas实现这一功能. 1.调整列的顺序 >>> df = pd.read_excel(r'D:/myExcel/1.xlsx') >>> df A B C D 0 bob 12 78 87 1 millor 15 92 21 >>> df.columns Index(['A', 'B', 'C', 'D'], dtype='object') # 这是最简单常用的一种方法,

随机推荐