11/15 LeetCode三道简单数组题：1313、1398、1365。
1313题加压缩编码。遍历一遍数组并不会增加时间复杂度，可以先遍历一遍找到目标数组的维度。
1398 按既定顺序创建目标数组。因为不确定插入的位置，所以使用while循环，元素后移更新，以达到更高的效率。
1365 有多少小于当前数字的数字。8大排序算法得学一学，技术和思路一样重要。官方还有第三种解法、二刷再搞。
1313 解压缩编码列表 题目描述 给你一个以行程长度编码压缩的整数列表 nums 。
考虑每对相邻的两个元素 [freq, val] = [nums[2i], nums[2 i+1]] （其中 i >= 0 ），每一对都表示解压后子列表中有 freq 个值为 val 的元素，你需要从左到右连接所有子列表以生成解压后的列表。
请你返回解压后的列表。
1 2 3 4 5 输入：nums = [1,2,3,4] 输出：[2,4,4,4] 解释：第一对 [1,2] 代表着 2 的出现频次为 1，所以生成数组 [2]。 第二对 [3,4] 代表着 4 的出现频次为 3，所以生成数组 [4,4,4]。 最后将它们串联到一起 [2] + [4,4,4] = [2,4,4,4]。
1 2 3 输入：nums = [1,1,2,3] 输出：[1,3,3] 来源：力扣（LeetCode）
我的解答 考虑减少迭代次数，并且数组的容量确定无法变化，借用 Arraylist 集合存储数组，然后转为数组。
结果就是 慢的一批。渣渣。
1 2 3 4 5 6 7 8 9 10 11 12 class Solution public int [] decompressRLElist(int [] nums) { ArrayList<Integer> list = new ArrayList<>(); for (int i=0 ;i<=nums.length/2 -1 ;i++){ for (int j = 1 ;j<=nums[2 *i];j++) { list.add(nums[2 *i+1 ]); } } int [] arr2 = list.stream().mapToInt(Integer::valueOf).toArray(); return arr2; } }
改进后的解答
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 class Solution public int [] decompressRLElist(int [] nums) { int length = 0 ; for (int i=0 ;i<= nums.length-1 ;i+=2 ){ length += nums[i]; } int [] arr = new int [length]; int index=0 ; for (int i=0 ;i<=nums.length-1 ;i+=2 ) { for (int j = 0 ; j <= nums[i]-1 ; j++) { arr[index] = nums[i+1 ]; index++; } } return arr; } }
扣友解答 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 class Solution public int [] decompressRLElist(int [] nums) { int len = 0 ; for (int i = 0 ; i < nums.length; i=i+2 ) { len += nums[i]; } int [] result = new int [len]; int index = 0 ; for (int i = 0 ; i < nums.length; i=i+2 ) { for (int j = 0 ; j < nums[i]; j++) { result[index] = nums[i+1 ]; index++; } } return result; } } 作者：liccil76
分析一波 ！！！ 记住：遍历一遍数组并不会增加时间复杂度。只有循环嵌套之后时间复杂度才会变为2次。
1398 按既定顺序创建目标数组 题目描述 给你两个整数数组 nums 和 index。你需要按照以下规则创建目标数组：
目标数组 target 最初为空。
题目保证数字插入位置总是存在。
1 2 3 4 5 6 7 8 9 10 输入：nums = [0,1,2,3,4], index = [0,1,2,2,1] 输出：[0,4,1,3,2] 解释： nums index target 0 0 [0] 1 1 [0,1] 2 2 [0,1,2] 3 2 [0,1,3,2] 4 1 [0,4,1,3,2] 来源：力扣（LeetCode）
我的解答 正常思路，因为不确定插入的位置，所以使用while循环，以达到更高的效率。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 class Solution public int [] createTargetArray(int [] nums, int [] index) { int [] arr = new int [nums.length]; for (int i=0 ;i<= nums.length-1 ;i++){ int j=i; while (index[i]<j){ arr[j]=arr[j-1 ]; j--; } arr[index[i]]=nums[i]; } return arr; } }
官方题解 因为插入的不确定性，使用list集合，最后再把list集合转为数组。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 class Solution public int [] createTargetArray(int [] nums, int [] index) { List<Integer> list = new ArrayList<Integer>(); for (int i = 0 ; i < nums.length; ++i) { list.add(index[i], nums[i]); } int [] ret = new int [nums.length]; for (int i = 0 ; i < nums.length; ++i) { ret[i] = list.get(i); } return ret; } } 作者：LeetCode-Solution
分析两波 爷的程序时间复杂度击败100%，很是流弊了。官方86%，不太行。
1365 有多少小于当前数字的数字 题目描述 给你一个数组 nums，对于其中每个元素 nums[i]，请你统计数组中比它小的所有数字的数目。
换而言之，对于每个 nums[i] 你必须计算出有效的 j 的数量，其中 j 满足 j != i 且 nums[j] < nums[i] 。
以数组形式返回答案。
1 2 3 4 5 6 7 8 输入：nums = [8,1,2,2,3] 输出：[4,0,1,1,3] 解释： 对于 nums[0]=8 存在四个比它小的数字：（1，2，2 和 3）。 对于 nums[1]=1 不存在比它小的数字。 对于 nums[2]=2 存在一个比它小的数字：（1）。 对于 nums[3]=2 存在一个比它小的数字：（1）。 对于 nums[4]=3 存在三个比它小的数字：（1，2 和 2）。
1 2 输入：nums = [6,5,4,8] 输出：[2,1,0,3]
1 2 输入：nums = [7,7,7,7] 输出：[0,0,0,0]
我的解答 最简单的暴力解法。时间复杂度O(n^2)，空间复杂度O(1)。
我简单的脑子和简单的知识面真只能想到这个。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 class Solution public int numIdenticalPairs (int [] nums) int re=0 ; for (int i=0 ;i<=nums.length-2 ;i++){ for (int j=i+1 ;j<=nums.length-1 ;j++){ if (nums[i]==nums[j]){ re++; } } } return re; } }
官方解答
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 class Solution public int [] smallerNumbersThanCurrent(int [] nums) { int n = nums.length; int [][] data = new int [n][2 ]; for (int i = 0 ; i < n; i++) { data[i][0 ] = nums[i]; data[i][1 ] = i; } Arrays.sort(data, new Comparator<int []>() { public int compare (int [] data1, int [] data2) return data1[0 ] - data2[0 ]; } }); int [] ret = new int [n]; int prev = -1 ; for (int i = 0 ; i < n; i++) { if (prev == -1 || data[i][0 ] != data[i - 1 ][0 ]) { prev = i; } ret[data[i][1 ]] = prev; } return ret; } } 作者：LeetCode-Solution
扣友解答1 作者说：解法二还可以更直观一点。实际上在排序数组中做“smaller than”的统计是很简单的，使用二维数组排序本质虽然相同，但是容易产生误解。
数组排序的操作涉及stream流、toArray()、sorted()，都需要学习巩固，包括后面集合转数组的操作，我并看不懂。
1 2 3 4 5 6 7 8 9 10 11 12 13 class Solution public int [] smallerNumbersThanCurrent(int [] nums) { Map<Integer, Integer> map = new HashMap<>(); int [] sorted = Arrays.stream(nums).sorted().toArray(); for (int i = 0 ; i < sorted.length; i++) { if (i == 0 || sorted[i] != sorted[i - 1 ]) { map.put(sorted[i], i); } } return Arrays.stream(nums).map(num -> map.get(num)).toArray(); } } 作者: Edward Elric
扣友解答2 作者说：思路差不多, 但是写法我的就很low了。
这个解法，我徒手看依然看不懂。包括copyofRange方法、containskey方法，但后面的那个循环让我理解了解答一的具体实现。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 public int [] smallerNumbersThanCurrent(int [] nums) { int [] temp = Arrays.copyOfRange(nums, 0 , nums.length); Arrays.sort(temp); Map<Integer, Integer> map = new HashMap<>(); for (int i = 0 ; i < temp.length; i++) { if (!map.containsKey(temp[i])) { map.put(temp[i], i); } } for (int i = 0 ; i < nums.length; i++) { temp[i] = map.get(nums[i]); } return temp; } 作者: NOCurd
分析三波 官方解答用二维数组排序并不是直接能想到的思维方式，反观评论里扣友的思路更为清晰。我之所以懂了思路仍然还是不能下手，是因为大部分集合、排序的操作我实在太过陌生，javaEE过了一遍、回头找笔记甚至也不能全不读懂、更别说自己独立的使用了。需要积累的还很多、慢慢的来。
还有就是，目前只能刷简单题，简单题不必过多赘述，以后只记录一下自己不会的题，一眼看出正确解答的编出来就完事了，现在这么菜都能做、以后也肯定可以做。
以上。