前端进阶之旅前端进阶之旅
基础篇
进阶篇
高频篇
精选篇
手写篇
原理篇
面经篇
自检篇
每日一题
  • 综合
    • 综合题型
    • 其他问题
    • 设计模式
    • 思维导图
    • 学习路线
  • 前端基础
    • HTTP
    • 浏览器
    • 计算机基础
  • 进阶学习
    • NPM工作流
    • Docker
    • Canvas
    • Node学习指南
    • 前端综合文章
  • 其他
    • Handbook
    • 职场话题
    • CSS可视化
小程序题库
公众号动态
博客动态
开发者导航
基础篇
进阶篇
高频篇
精选篇
手写篇
原理篇
面经篇
自检篇
每日一题
  • 综合
    • 综合题型
    • 其他问题
    • 设计模式
    • 思维导图
    • 学习路线
  • 前端基础
    • HTTP
    • 浏览器
    • 计算机基础
  • 进阶学习
    • NPM工作流
    • Docker
    • Canvas
    • Node学习指南
    • 前端综合文章
  • 其他
    • Handbook
    • 职场话题
    • CSS可视化
小程序题库
公众号动态
博客动态
开发者导航
  • React专栏

    • React组合式开发实战

      • 前端开发的四个时代
      • 企业管理系统的前世今生
      • 可视化页面搭建工具
      • 实战篇 01:开发前准备
      • 实战篇 02:项目脚手架
      • 实战篇 03:页面布局方案
      • 实战篇 04:权限管理机制
      • 实战篇 05:菜单匹配逻辑
      • 实战篇 06:消息通知设计
      • 实战篇 07:多语言支持
      • 继往开来:可视化页面搭建工具
    • React Hooks与Immutable实战

    • React SSR服务端渲染与同构实践

    • IM聊天系统前端开发实践

    • 微前端开发实战

    • React进阶实践

  • Vue专栏

  • 移动端专栏

  • Node专栏

  • 前端工程化专栏

  • 算法专栏

  • Typescript专栏

  • 其他专栏

完整面试题地址:
作者:程序员poetry
扫码关注作者公众号:「前端进阶之旅」 每天分享技术干货
前端进阶之旅公众号二维码

# 题目

在数组中的两个数字,如果前面一个数字大于后面的数字,则这两个数字组成一个逆序对。输入一个数组,求出这个数组中的逆序对的总数P。

# 思路

使用暴力法:从第一个数开始,依次和后面每一个数字进行比较记录逆序对的个数,时间复杂度O(n2)

使用分治的细想:

若没了解过归并排序,建议先熟悉 归并排序算法再来看本题。

直接将归并排序进行改进,把数据分成N个小数组。

合并数组 left - mid , mid+1 - right,合并时, 若array[leftIndex] > array[rightIndex] ,则比右边 rightIndex-mid个数大

count += rightIndex-mid

注意和归并排序的区别: 归并排序是合并数组数从小数开始,而本题是从大数开始。

时间复杂度O(nlogn)

空间复杂度O(n)

# 代码

    function InversePairs(data) {
      return mergeSort(data, 0, data.length - 1, []);
    }

    function mergeSort(array, left, right, temp) {
      if (left < right) {
        const mid = parseInt((left + right) / 2);
        const l = mergeSort(array, left, mid, temp);
        const r = mergeSort(array, mid + 1, right, temp);
        const m = merge(array, left, right, mid, temp);
        return l + m + r;
      } else {
        return 0;
      }
    }

    function merge(array, left, right, mid, temp) {
      let leftIndex = mid;
      let rightIndex = right;
      let tempIndex = right - left;
      let count = 0;
      while (leftIndex >= left && rightIndex > mid) {
        if (array[leftIndex] > array[rightIndex]) {
          count += (rightIndex - mid);
          temp[tempIndex--] = array[leftIndex--];
        } else {
          temp[tempIndex--] = array[rightIndex--];
        }
      }
      while (leftIndex >= left) {
        temp[tempIndex--] = array[leftIndex--];
      }
      while (rightIndex > mid) {
        temp[tempIndex--] = array[rightIndex--];
      }
      tempIndex = 0;
      for (let i = left; i <= right; i++) {
        array[i] = temp[tempIndex++];
      }
      return count;
    }
@前端进阶之旅: 代码已经复制到剪贴板

# 考察点

  • 数组
  • 分治
fe
基础篇
进阶篇
高频篇
精选篇
手写篇
原理篇
面经篇
自检篇
每日一题
  • 综合
    • 综合题型
    • 其他问题
    • 设计模式
    • 思维导图
    • 学习路线
  • 前端基础
    • HTTP
    • 浏览器
    • 计算机基础
  • 进阶学习
    • NPM工作流
    • Docker
    • Canvas
    • Node学习指南
    • 前端综合文章
  • 其他
    • Handbook
    • 职场话题
    • CSS可视化
小程序题库
公众号动态
博客动态
开发者导航
  • React专栏

    • React组合式开发实战

      • 前端开发的四个时代
      • 企业管理系统的前世今生
      • 可视化页面搭建工具
      • 实战篇 01:开发前准备
      • 实战篇 02:项目脚手架
      • 实战篇 03:页面布局方案
      • 实战篇 04:权限管理机制
      • 实战篇 05:菜单匹配逻辑
      • 实战篇 06:消息通知设计
      • 实战篇 07:多语言支持
      • 继往开来:可视化页面搭建工具
    • React Hooks与Immutable实战

    • React SSR服务端渲染与同构实践

    • IM聊天系统前端开发实践

    • 微前端开发实战

    • React进阶实践

  • Vue专栏

  • 移动端专栏

  • Node专栏

  • 前端工程化专栏

  • 算法专栏

  • Typescript专栏

  • 其他专栏