星空网 > 软件开发 > 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的分析

315. Count of Smaller Numbers After Self315. Count of Smaller Numbers After Self

树状数组图

315. Count of Smaller Numbers After Self

 




原标题:315. Count of Smaller Numbers After Self

关键词:

*特别声明:以上内容来自于网络收集,著作权属原作者所有,如有侵权,请联系我们: admin#shaoqun.com (#换成@)。

fba怎么发:https://www.goluckyvip.com/tag/20285.html
fba怎么发货:https://www.goluckyvip.com/tag/20286.html
fba怎么跟卖:https://www.goluckyvip.com/tag/20287.html
fba怎么计算:https://www.goluckyvip.com/tag/20288.html
fba怎么建仓:https://www.goluckyvip.com/tag/20289.html
中东发展前景:https://www.goluckyvip.com/tag/2029.html
怎样做出一个有利可图的SaaS产品?:https://www.kjdsnews.com/a/1836639.html
【再放信号】美国Etsy即将放开中国卖家入驻,官方邮件你收到了吗?:https://www.kjdsnews.com/a/1836640.html
相关文章
我的浏览记录
最新相关资讯
海外公司注册 | 跨境电商服务平台 | 深圳旅行社 | 东南亚物流