Array 1313. 解压缩编码列表

2020-11-03

给你一个以行程长度编码压缩的整数列表 nums 。

考虑每对相邻的两个元素[freq, val] = [nums[2*i], nums[2*i+1]]（其中 i >= 0 ），每一对都表示解压后子列表中有 freq 个值为 val 的元素，你需要从左到右连接所有子列表以生成解压后的列表。

请你返回解压后的列表。

思路：

原数两个元素为 1 组，第一个元素为出现的次数，第二个是出现的数值。首先计算出解压之后列表的长度，然后以步长为 2 来解压原列表。

public int[] decompressRLElist(int[] nums) {
       // 计算解压后数组的长度
       int len = 0;
       for(int i = 0;i < nums.length;i=i+2 ){
           len += nums[i];
       }
       int[] res = new int [len];
       int index = 0;
       for(int i = 0;i < nums.length;i=i+2 ){
           for(int j = 0;j < nums[i];j++){
               res[index] = nums[i+1];
               index++;
           }
       }
       return res;
   }

时间复杂度：$o(n + m(num数组中所有下标为偶数的元素和))$

空间复杂度：$o(1)$

1365 有多少小于当前数字的数字

给你一个数组 nums，对于其中每个元素 nums[i]，请你统计数组中比它小的所有数字的数目。

换而言之，对于每个 nums[i] 你必须计算出有效的 j 的数量，其中 j 满足 j != i 且 nums[j] < nums[i] 。

以数组形式返回答案。

思路：

依次循环，暴力破解

public int[] smallerNumbersThanCurrent(int[] nums) {
    int len = nums.length;
    int [] res = new int [len];
    for(int i = 0;i<len;i++){
        int count = 0;
        for(int j = 0;j < len;j++){
            if(nums[i] > nums[j]) count++;
        }
    res[i] = count;
    }
    return res;
}

时间复杂度：$O(N^2)$，其中 N 为数组的长度。
空间复杂度：$O(1)$。注意我们不计算答案数组的空间占用。

方法二快速排序

将数组排序，利用 Array.sort 实现 Comparator 从大到小排序。然后每个左边元素的个数就是小于他的个数。

但是原数组经过排序之后，顺序就会打乱，无法标记之前的位置。因此，一开始将原数组存储在一个二维数组里面，一列是数值，一列是下标。对二维数组的数值列进行排序。

public int[] smallerNumbersThanCurrent(int[] nums) {
    int len =  nums.length;

    // 建立一个二维数组
    int[][] data = new int [len][2];
    for(int i = 0;i < len; i++) {
        
            data[i][0] = nums[i];
            data[i][1] = i;
        
    }
    // 按从小到大的顺序
    // Arrays.sort(nums);
    Arrays.sort(data new Comparator<int[]>() {
        public int compare(int[] data1,int[] data2){
            return data1[0] - data2[0];
        }
    })

    int[] ret = new int [len];
    // 记录下标
    int index = -1;
    for(int i = 0;i< len;i++){
        // 如果两个数相等 拥有相同的 index ，第一个数的 index 为0
        if(i == 0 || nums[i] != nums[i-1]){
            index = i;
        }
        // 此处的data 已经经过排序了 data[i][1] 是依次输出 data 的下标列
       ret[data[i][1]] = index; 
    }
    return ret;
}

举例，比如原始的 nums: [1,4,2,6,2],初试建立的 data 是[[1,0],[4,1],[2,2],[6,3],[2,4]],排序之后的data 是 [[1,0],[2,2],[2,4],[4,1],[6,3]]，在 comparator 里面，compare 比较的是每个 data 项里的第一个元素。

ret
[0,0,0,0,0]
[0,0,1,0,0]
[0,0,1,0,1]
[0,3,1,0,1]
[0,3,1,4,1] ----- [1,4,2,6,2] 原始数组

方法三计数排序

到数组元素的值域为[0,100]，所以可以考虑建立一个频次数组 cnt ，cnt[i] 表示数字 i 出现的次数。那么对于数字 ii 而言，小于它的数目就为 cnt[0…i-1] 的总和。计数排序相比于冒泡排序这类（基于数字比较）速度快

public int[] smallerNumbersThanCurrent(int[] nums) {

        // 计数排序
        int len = nums.length;
        // 建立一个统计数组 0-100
        int [] cnt = new int [101];
        for(int i = 0;i < len;i++){
            // 计算出现次数
            cnt[nums[i]]++;
        }
        // 对统计数组做变形 后面的元素等于前面的元素之和
        // cnt统计数组现在的意思：i 在所有元素中是第 cnt[i]位
        for(int i =1;i < 101;i++){
            cnt[i] += cnt[i-1];
        }
         int [] res = new int [len];
          for(int i =0;i < len;i++){
            //   统计小于元素的数目，不算本身 -1 
              res[i] = nums[i]==0 ? 0 : cnt[nums[i] - 1];
          }
          return res;
    }

时间复杂度：两次循环 2N + M $o(n+m)$.

空间复杂度：除了需要存储结果的数组外，还有一个统计数组。

1365 有多少小于当前数字的数字

方法二 快速排序

方法三 计数排序

方法二快速排序

方法三计数排序