leetcode：1313. 解压缩编码列表

朴灿烈づ我的快乐病毒、 2023-07-25 09:51 3阅读 0赞

# 题目来源 #

*  [1313. 解压缩编码列表][1313.]

# 题目详情 #

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAT2NlYW4mJlN0YXI_size_20_color_FFFFFF_t_70_g_se_x_16]

![在这里插入图片描述][e23a2cff6a01473e8442889894bce7b6.png]

# 题目解答 #

## 模拟 ##

### C++ ###

vector<int> decompressRLElist(vector<int>& nums) {
        
        vector<int> vet;
    
        int freq, val;
        for(int i = 0; i < nums.size(); i = i+2){
        
            freq = nums[i];
            val = nums[i + 1];
    
            for(int j = 0; j < freq; j++){
        
                vet.emplace_back(val);
            }
        }
    
        return vet;
    }

![在这里插入图片描述][636949d469d743ca9257df71f7a12aac.png]

## java ##

public static int[] decompressRLElist(int[] nums) {
        
            if (nums == null || nums.length == 0 || nums.length % 2 != 0){
        
                return null;
            }
    
            int[][] map = new int[nums.length/2][2];
    
            int a = 0;
            int length = 0;
            for(int i = 1; i < nums.length; i = i + 2){
        
                int freq = nums[i - 1];
                int value = nums[i];
    
                map[a][0] = freq;
                map[a][1] = value;
                a++;
    
                length = length + freq;
            }
    
            // N
    
            int[] res = new int[length];
            int start = 0;
            for (int i = 0; i < map.length; i++){
        
                int freq = map[i][0];
                int value = map[i][1];
    
                System.out.println(freq + " " + value);
    
                // 注意这里赋值的时候的起始索引和结束索引
                for (int j = start; j < start +  freq; j++){
        
                    res[j] = value;
                }
                start = start + freq;
            }
    
    
            return res;
        }

复杂度N

# 解答\[2ms\] #

public static int[] decompressRLElist(int[] nums) {
        
            if (nums == null || nums.length == 0 || nums.length % 2 != 0){
        
                return null;
            }
    
            // 先求出新数组的长度
            int length = 0;
            for(int i = 0; i < nums.length; i = i + 2){
        
                length = length + nums[i];
            }
    
            // 填充
            int[] res = new int[length];
            int s = 0;  //
            for (int i = 0; i < nums.length; i = i + 2){
        
                int a = nums[i]; //
                while (a > 0){
        
                    res[s] = nums[i+1];
                    a--;
                    s++;
                }
            }
    
    
            return res;
        }

# solution 【2ms，但是空间复杂度最大】 #

数组长度说明：因为题目说明了数组长度nums.length最大为100,数据值nums\[i\]最大100,假设都达到了最大值，则数据规模上限为100个数里有100个100，其中题目所说的a有50个100，说明存储最终结果的数组最大长度为50\*100=5000，得初始化容量int\[\] ans = new int\[5000\];

解题思路：

直接遍历nums数组，步长为2( i+=2 )  
从结果数组ans的填充下标开始位置fromIndex填充到toIndex = from + nums\[i\]位置  
遍历结束，返回数组前toIndex个数

if (nums == null || nums.length == 0 || nums.length % 2 != 0){
        
                return null;
            }
    
    
            int[] res = new int[50 * 100];
    
            // sindex 记录为填充的开始索引
            // 开始索引和结束索引的位置
            int toindex = 0;  // 结束索引
            for (int i = 0, fromindex = 0; i < nums.length; i = i + 2){
        
                toindex = fromindex + nums[i];  // 结束索引 = 开始索引 + 元素长度
                while (fromindex < toindex){
        
                    res[fromindex++] = nums[i+1];
                }
            }
    
            return Arrays.copyOf(res, toindex);

[1313.]: https://leetcode-cn.com/problems/decompress-run-length-encoded-list/
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAT2NlYW4mJlN0YXI_size_20_color_FFFFFF_t_70_g_se_x_16]: /images/20230528/ad6320d8d82c46b8971023005f48f9aa.png
[e23a2cff6a01473e8442889894bce7b6.png]: /images/20230528/1919c41c87ef4dda8aed2e7b8b4b1db9.png
[636949d469d743ca9257df71f7a12aac.png]: /images/20230528/4a01f495e18b4a999f46ee4105a573bf.png