Array格式化

admin管理员组

文章数量:1530354

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