广联达 7月29第二题
做这道题的心路历程：
1、模拟操作，一个boolean 一次遍历如果没有操作退出 时间复杂度 最好O（n） 最差O（n*n）
2、用set来防止重复，后面想到要取到索引，上了map ac
private static void compact(int[] arr) {
// value , index 存值的位置，方便索引 因为不允许有重复的值
Map<Integer, Integer> map = new HashMap<>();
// 这个for里面还可以缩减代码，笔试时没想那么多，按照思路写 缩减看下面
for (int i = 0; i < arr.length; i++) {
if (map.containsKey(arr[i])) {
arr[map.get(arr[i])] = -1;
map.remove(arr[i]);
arr[i] = 2 * arr[i];
while (map.containsKey(arr[i])) {
arr[map.get(arr[i])] = -1;
map.remove(arr[i]);
arr[i] = 2 * arr[i];
}
map.put(arr[i], i);
} else {
map.put(arr[i], i);
}
}
for (int num : arr) {
if (num != -1) {
System.out.print(num + " ");
}
}
}
// 如果缩减代码
for (int i = 0; i < arr.length; i++) {
while (map.containsKey(arr[i])) {
arr[map.get(arr[i])] = -1;
map.remove(arr[i]);
arr[i] = 2 * arr[i];
}
map.put(arr[i], i);
}
