【排序算法运用】剑指 Offer 51. 数组中的逆序对

共以下 8 个回答

• lQl 永久会员 2025年1月18日 上午10:34

  class Solution {
      int cnt = 0;
  
      public int reversePairs(int[] record) {
          mergeSort(record, 0, record.length - 1);
          return cnt;
      }
  
      private void mergeSort(int[] record, int l, int r) {
          if (l >= r)
              return;
          int m = (l + r) / 2;
          mergeSort(record, l, m);
          mergeSort(record, m + 1, r);
          merge(record, l, m, r);
      }
  
      public void merge(int[] record, int l, int m, int r) {
          int[] tmp = new int[r - l + 1];
          int i = l;
          int j = m + 1;
          int t = 0;
          while (i <= m && j <= r) {
              if (record[i] <= record[j]) {
                  tmp[t++] = record[i++];
              } else {
                  cnt += m - i + 1;
                  tmp[t++] = record[j++];
              }
          }
          while (i <= m) {
              tmp[t++] = record[i++];
          }
          while (j <= r) {
              tmp[t++] = record[j++];
          }
          for (int k = 0; k < tmp.length; k++) {
              record[l + k] = tmp[k];
          }
      }
  }
  

  时间复杂度O(nlogn)
  空间复杂度O(n)

  0 赞同 0 条回复

  登录以回复
• Xiang. 永久会员 2024年12月22日 下午7:23

  class Solution {
      public int reversePairs(int[] record) {
          if(record==null||record.length<=1) return 0;
          return mergeSort(record,0,record.length-1);
      }
  
      int mergeSort(int[] record,int left,int right){
          if(left<right){
              int mid=(left+right)/2;
              int x1=mergeSort(record,left,mid);
              int x2=mergeSort(record,mid+1,right);
              int x3=merge(record,left,mid,right);
              return x1+x2+x3;
          }else return 0;
      }
      int merge(int[] record,int left,int mid,int right){
          int count=0;
          int len1=mid-left+1;
          int len2=right-mid;
          int[] leftArr=new int[len1];
          int[] rightArr=new int[len2];
          for(int i=0;i<len1;i++) leftArr[i]=record[left+i];
          for(int j=0;j<len2;j++) rightArr[j]=record[mid+1+j];
          int i=0;
          int j=0;
          int k=left;
          while(i<len1&&j<len2){
              if(leftArr[i]<=rightArr[j]){
                  record[k++]=leftArr[i++];
              }else{
                  record[k++]=rightArr[j++];
                  count=count+(len1-i);
              }
          }
          while(i<len1) record[k++]=leftArr[i++];
          while(j<len2) record[k++]=rightArr[j++];
          return count;
      }
  }
  时间复杂度：O（nlogn）
  空间复杂度：O（n）
  

  0 赞同 0 条回复

  登录以回复
• 陆狗陆狗 普通 2024年12月20日 下午10:39

  解题思路
  – 比如数组[9, 7, 5, 4,6]，我们在使用归并排序（最终变成升序的过程中）的合并阶段，其实就会去两两比较是否逆序，如果逆序需要交换位置。
  – 第一层合并 比如[9]和[7] 就是逆序1个，[5]和[4]就是逆序1个,[6]是逆序0个。（1+1+0=2）
  – 第二层合并 [7,9] 和[4,5]，7>5,那么7、9(…)都大于4,逆序2个；7>5，那么7、9(…)都大于4，逆序2个 。（2+2=4）
  – 第三层合并[4,5,7,9] 和6 ，从7开始，7、9(…)都大于6，逆序2个。（2）
  – 总共逆序个数=2+4+2=8个
  【题解1】

  class Solution {
  
      int count = 0;
      // 【错误点】tmpt最好是定义一个全局的而不是在每一次合并merge的时候单独定义，因为是递归调用，容易oom
      // 定义一个临时数组来存放合并后的数据，大小和元素相同是为了方便移动数据
      int[] tmpt;
  
      public int reversePairs(int[] record) {
          // 逆序对的总数=归并排序中交换了前后位置的次数
          // 边界
          if (record.length <= 1) {
              return 0;
          }
          tmpt = new int[record.length];
          mergeSort(record, 0, record.length - 1);
          return count;
  
      }
  
      public void mergeSort(int[] arr, int left, int right) {
  
          if (left < right) {
              // 1、拆分
              int mid = (left + right) / 2;
              mergeSort(arr, left, mid);
              // 多余的给右边
              mergeSort(arr, mid + 1, right);
              // 2、合并
              merge(arr, left, mid, right);
          }
  
      }
  
      public void merge(int[] arr, int left, int mid, int right) {
          int i = left;
          int j = mid + 1;
          int cur = left;
          while (i <= mid && j <= right) {
              if (arr[i] > arr[j]) {
                  // 右边数组的更小,左边更大，需要交换
                  // 左边的剩余个数全部都比当前右边这个值大
                  count = count + (mid - i + 1);
                  tmpt[cur++] = arr[j++];
              } else {
                  // 左边数组更小，右边更大，不需要交换
                  tmpt[cur++] = arr[i++];
              }
          }
          // 左边数组或者右边数组剩余的部分
          while (i <= mid) {
              tmpt[cur++] = arr[i++];
          }
          while (j <= right) {
              tmpt[cur++] = arr[j++];
          }
          // 临时数组的数据放置到原本数组中
          for (int m = left; m <= right; m++) {
              arr[m] = tmpt[m];
          }
      }
  }
  

  • 错误点1：tmpt最好是定义一个全局的而不是在每一次合并merge的时候单独定义，因为是递归调用，容易oom

  0 赞同 0 条回复

  登录以回复
• Kisara 普通 2024年12月18日 下午6:06

  归并排序

  class Solution {
      int count=0;
      int[] temp;
      public int reversePairs(int[] record) {
          mergeSort(record,0,record.length-1);
          return count;
      }
  
      public void mergeSort(int[] record,int left,int right){
          if(left>=right) return ;
          int mid=(left+right)/2;
          //划分数组，直到只剩一个元素
          mergeSort(record,left,mid);
          mergeSort(record,mid+1,right);
  
          //开始合并
          temp=new int[right-left+1];
          //指向左数组
          int i=left;
          //指向右数组
          int j=mid+1;
          //指向临时数组
          int t=0;
  
          //当左右数组都有元素的时候执行
          while(i<=mid&&j<=right){
              if(record[i]<=record[j]){
                  temp[t++]=record[i++];
              }else {
              //临时数组都是有序的,i对应的左边元素如果大于右边j对应的元素,那么i左边的所有元素都能和=右边的j组成逆序数,所以count+=mid-i+1
                  count+=mid-i+1;
                  temp[t++]=record[j++];
              }
          }
          
          //如果右数组没了，直接把左数组接上
          while(i<=mid){
              temp[t++]=record[i++];
          }
          //如果左数组没了，直接把右数组接上
          while(j<=right){
              temp[t++]=record[j++];
          }
          //根据临时数组更新原数组
          for(int q = 0;q<temp.length;q++){
              record[left+q]=temp[q];
          }
         }
      }
  

  0 赞同 0 条回复

  登录以回复
• 苯庸 普通 2024年12月18日 下午12:34

  class Solution {
  int cnt = 0;
  public int reversePairs(int[] record) {
  mergeSort(record, 0, record.length-1);
  return cnt;
  }

  void mergeSort(int[] nums, int l, int r){
      if(l >= r) return;
      int m = (l + r) / 2;
      mergeSort(nums, l, m);
      mergeSort(nums, m+1, r);
      merge(nums, l, m, r);
  }
  
  void merge(int[] nums, int l, int m, int r){
      int[] temp = new int[r-l+1];
      int i = l, j = m+1;
      int k = 0;
      while(i <= m && j <= r){
          if(nums[i] <= nums[j]){
              temp[k++] = nums[i++];
          }else{
              cnt += m-i+1;
              temp[k++] = nums[j++];
          }
      }
      while(i <= m){
          temp[k++] = nums[i++];
      }
      while(j <= r){
          temp[k++] = nums[j++];
      }
      for(int z = 0; z < temp.length; z++){
          nums[z+l] = temp[z];
      }
  }
  

  }
  时间：O（lgn）
  空间：O（n）

  0 赞同 0 条回复

  登录以回复
• Aatorx 永久会员 2024年12月17日 下午5:16

  class Solution {
  public:
      int reversePairs(vector<int>& record) {
          vector<int> temp(record.size());
          return mergesort(record, 0, record.size() - 1, temp);
      }
      int mergesort(vector<int>& record, int l, int r, vector<int>& temp) {
          if(l >= r) {
              return 0;
          }
          int m = (r - l) / 2 + l;
          int res = mergesort(record, l, m, temp) + mergesort(record, m + 1, r, temp);
          temp = record;
          int k = m + 1;
          int x = l;
          for(int i = l; i <= r; i++) {
              if(x == m + 1) {
                  record[i] = temp[k];
                  k++;
              }
              else if(k == r + 1 || temp[x] <= temp[k]) {
                  record[i] = temp[x];
                  x++;
              }else {
                  record[i] = temp[k];
                  k++;
                  res += m - x + 1;
              }
          }
          return res;
      }
  };
  

  归并排序，在排序的过程中统计逆序对数量。
  时间复杂度O(Nlogn)，空间复杂度O(N)。

  0 赞同 0 条回复

  登录以回复
• 月下足迹 普通 2024年12月17日 下午1:36

  class Solution {
  public int reversePairs(int[] record) {
  if (record null || record.length < 2) {
  return 0;
  }
  // 使用归并排序来计算逆序对
  return mergeSort(record, 0, record.length – 1);
  }

  // 归并排序并统计逆序对
  private int mergeSort(int[] arr, int left, int right) {
      if (left >= right) {
          return 0;  // 基本情况，当子数组只有一个元素时，逆序对数为0
      }
  
      int mid = left + (right - left) / 2;
  
      // 递归地分割数组
      int count = mergeSort(arr, left, mid) + mergeSort(arr, mid + 1, right);
  
      // 合并两个排序好的子数组，并统计逆序对
      count += merge(arr, left, mid, right);
  
      return count;
  }
  
  // 合并两个已排序的子数组，并统计逆序对
  private int merge(int[] arr, int left, int mid, int right) {
      int count = 0;
  
      // 创建一个临时数组来存储排序后的元素
      int[] temp = new int[right - left + 1];
  
      int i = left, j = mid + 1, k = 0;
  
      // 统计逆序对的数量
      while (i <= mid && j <= right) {
          if (arr[i] <= arr[j]) {
              temp[k++] = arr[i++];
          } else {
              temp[k++] = arr[j++];
              count += (mid - i + 1);  // 统计逆序对，所有左边剩余的元素都大于arr[j]
          }
      }
  
      // 将剩余的左子数组元素复制到临时数组
      while (i <= mid) {
          temp[k++] = arr[i++];
      }
  
      // 将剩余的右子数组元素复制到临时数组
      while (j <= right) {
          temp[k++] = arr[j++];
      }
  
      // 将临时数组的内容复制回原数组
      System.arraycopy(temp, 0, arr, left, temp.length);
  
      return count;
  }
  

  }

  0 赞同 0 条回复

  登录以回复
• 迢迢星野 普通 2024年12月16日 下午10:15

  class Solution {
      int[] record, tmp;
      /**
       * 在股票交易中，如果前一天的股价高于后一天的股价，则可以认为存在一个「交易逆序对」。请设计一个程序，输入一段时间内的股票交易记录 
       * record，返回其中存在的「交易逆序对」总数。
       * 
       * 题意解读：计算逆序对的个数
       * 方法一：归并排序
       *      归并排序是与 逆序对 息息相关的。
       *      在合并阶段，本质上是合并两个排序数组的过程，每当遇到 左子数组的当前元素 > 右子数组的当前元素 时，意味着：[左子数组当前元素，
       *   左子数组末尾元素] 与 右子数组当前元素 都构成逆序对。
       *   
       *      归并排序：
       *          1. 终止条件：l >= r，子数组长度为 1 时，终止划分；
       *          2. 递归划分：计算数组中点 m，递归划分左子数组和右子数组
       *          3. 合并并统计逆序对：
       *              3.1 先将 [l,r] 内的元素存入到临时数组 tmp 中
       *              3.2 循环合并，设置双指针 i、j，分别指向左子数组和右子数组的首元素：
       *                  i == m + 1 时，左子数组合并完，因此添加右子数组当前元素 tmp[j]，并执行 j = j + 1
       *                  j == r 时，表示右子数组合并完，因此添加左子数组当前元素 tmp[i]，并执行 i = i + 1
       *                  tmp[i] <= tmp[j] 时，添加左子数组当前元素 tmp[i]，i++
       *                  tmp[i] > tmp[j] 时，说明左子数组的当前元素到其末尾元素，与右子数组的当前元素 都构成逆序对，记录其个数即可 m - i + 1;
       *           4. 返回直至目前的逆序对总数 res ；
       * @param record
       * @return
       */
      public int reversePairs(int[] record) {
          this.record = record;
          tmp = new int[record.length];
  
          return mergeSort(0, record.length - 1);
      }
  
      private int mergeSort(int l, int r) {
          if (l >= r) {
              return 0;
          }
  
          int m = l + (r - l) / 2;
          // 递归
          int res = mergeSort(l, m) + mergeSort(m + 1, r);
  
          // 合并
          // 复制 record 的值，用 tmp 进行归并
          for (int k = l; k <= r; k++) {
              tmp[k] = record[k];
          }
          int i = l, j = m + 1;
          // 将 tmp 的 [l, r] 进行排序
          for (int k = l; k <= r; k++) {
              if (i == m + 1) {
                  // 左子数组合并完成，将 右子数组 剩余元素存入 tmp 中
                  record[k] = tmp[j];
                  j++;
              }else if (j == r + 1) {
                  // 右子数组合并完成，将 左子数组 剩余元素存入 tmp 中
                  record[k] = tmp[i];
                  i++;
              }else if (tmp[i] <= tmp[j]) {
                  // 左子数组的当前元素 <= 右子数组的当前元素，说明左子数组的当前元素合并完成，向后继续合并
                  record[k] = tmp[i];
                  i++;
              }else if (tmp[i] > tmp[j]) {
                  // [左子数组的当前元素, 左子数组的末尾元素] 与 右子数组的当前元素 都构成逆序对，记录其总数
                  record[k] = tmp[j];
                  j++;
                  res += m - i + 1;
              }
          }
          return res;
      }
  }
  

  思路：归并排序，具体思路参考注释。
  时间复杂度：O(nlogn)
  空间复杂度：O(n)

  0 赞同 0 条回复

  登录以回复