你的位置:首页 > Java教程

[Java教程]315. Count of Smaller Numbers After Self


 You are given an integer array nums and you have to return a new counts array. The counts array has the property where counts[i] is the number of smaller elements to the right of nums[i].

Example:

Given nums = [5, 2, 6, 1]To the right of 5 there are 2 smaller elements (2 and 1).To the right of 2 there is only 1 smaller element (1).To the right of 6 there is 1 smaller element (1).To the right of 1 there is 0 smaller element.

Return the array [2, 1, 1, 0]

public class Solution {  public List<Integer> countSmaller(int[] nums) {    // 求得nums在按序排列的数组中的脚标位置    int[] temp = nums.clone();    Arrays.sort(temp);    for (int i = 0; i < temp.length; i++) {      nums[i] = Arrays.binarySearch(temp, nums[i]);    }    // 这里用Integer是为了使用Arrays.asList    Integer[] ans = new Integer[temp.length];    int[] bit = new int[temp.length];    // 遍历的时候使用逆序是因为位于数组最后面的数,逆序程度是最低的    for (int i = temp.length-1; i >= 0; i--) {      /**       * 用bit数组的前num[i]项和作为逆序程度       *       * 最后一位的逆序永远是0        * 次高位的逆序要么是1要么是0,最大值只能是1       * query方法正好保证了这点。       *   它查询bit数组中前nums[i]项的和       *   如果最高位比次高位要小,那么计算次高位项的和就会加1,相反就不回家       */      ans[i] = query(bit,nums[i]);      /**       * 修改那条链上的数据+1       */      add(bit,nums[i]+1,1);    }        return Arrays.asList(ans);  }    /**   * 功能:   *    修改bit数组脚标i对应的链上的数据   *   (因为求前n项和,是根据那几个数来求的,所以改动一个数要同时改动那几个数)   * @param bit 树状数组   * @param i  数组脚标   * @param val 脚标所对应的树枝要修改的值   */  private void add(int[] bit, int i, int val) {    for (;i<bit.length;i+=lowbit(i)) {      bit[i]+=val;    }  }    /**   * 查询bit数组中前i项的和   * @param bit 树状数组   * @param i  数组脚标   * @return   */  private Integer query(int[] bit, int i) {    int ans = 0;    for (;i>0;i-=lowbit(i)) {      ans += bit[i];    }    return ans;  }  /**   *  求二进制的i中第一个1对应的十进制值   * @param i   * @return i转化为二进制之后第一个1所对应的值   */  private int lowbit(int i) {    return i&(-i);  }}

简单的解释一下ans数组的产生:

只要后面一位比前面一位要小,那么前面一位求前n项和的时候就会多加一个1.所以加了多少个1,逆序数就有几个。

前n项和的值中每一个1代表了一个逆序数。

分别对:896859    896853的分析

树状数组图