admin管理员组文章数量:1571578
Array格式化,是一种处理数组值的定位问题的数据处理办法 ,把源数组的值当做临时数组的下标,把源数组值出现的次数 统计为临时数组的值 。
这样做虽然会丢失源数组的顺序,但能突出源数据的一些关键值和他们出现的顺序,还可以避免双层循环。
使用场景
我们有时候会遇到定范围的数组值的数组,比如果char[]或者我们已知数据范围的int[]。我们可是使用Array格式化来处理数据。
理解要点
Array格式化是把数据的可能的值一一列出来,摆在桌子上,用Array的下标存值,用Array的值存数量。
某个值变则找到原值的下标的数量-1数量,变后的值的地方+1数量
和我之前介绍过的Map格式化的差别是,此种数据格式化更突出key的排列顺序和取值。
可以省下一个排序,并且能体现惊人的脑回路。
int[] A = {XXXXXX};
int[] number = new int[A数组可能的取值数量];
for (int t : A) {
number[t]++;
}
如代码所示,A数组变成了number数组,number的长度是可以自己选取。超界限的话,相当于A数组中有数据没统计上。
LeetCode真题
给定一个整数数组 A,我们只能用以下方法修改该数组:我们选择某个个索引 i 并将 A[i] 替换为 -A[i],然后总共重复这个过程 K 次。(我们可以多次选择同一个索引 i。)
以这种方式修改数组后,返回数组可能的最大和。
示例 1:
输入:A = [4,2,3], K = 1
输出:5
解释:选择索引 (1,) ,然后 A 变为 [4,-2,3]。
示例 2:
输入:A = [3,-1,0,2], K = 3
输出:6
解释:选择索引 (1, 2, 2) ,然后 A 变为 [3,1,0,2]。
示例 3:
输入:A = [2,-3,-1,5,-4], K = 2
输出:13
解释:选择索引 (1, 4) ,然后 A 变为 [2,3,-1,5,4]。
提示:
1 <= A.length <= 10000
1 <= K <= 10000
-100 <= A[i] <= 100
来源:力扣(LeetCode)
链接:https://leetcode-cn/problems/maximize-sum-of-array-after-k-negations
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
class Solution {
public int largestSumAfterKNegations(int[] A, int K) {
int[] number = new int[201];
for (int t : A) {
number[t + 100]++;
}
int i = 0;
while (K > 0) {
while (number[i] == 0)
i++;
number[i]--;
number[200 - i]++;
if (i > 100) {
i = 200 - i;
}
K--;
}
int sum = 0;
for (int j = i; j <number.length ; j++) {
sum += (j-100)*number[j];
}
return sum;
}
}
速度远超普通写法。因为我们不需要排序,而是通过了Array格式化找到了全部最小值,在改变最小值后还能够迅速的找到下一个最小值,而不是再去打擂台去找。
本文标签: Array
版权声明:本文标题:Array格式化 内容由热心网友自发贡献,该文观点仅代表作者本人, 转载请联系作者并注明出处:https://www.elefans.com/dongtai/1726469770a1071981.html, 本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容,一经查实,本站将立刻删除。
发表评论