对ArrayList进行排序，但保持原始索引的顺序

Question

有两个int数组和一个名为costs和shipping的数组列表。我想要一个总价从最小到最大的ArrayList(例如成本[0]+运费[0](，但重新排序两个int数组以匹配ArrayList:

Scanner scan = new Scanner(System.in);
int n = scan.nextInt();
int[] costs = new int[n];
int[] shipping = new int[n];
ArrayList<Integer> totalCosts = new ArrayList<>();

例如，假设成本是[1，5，2，3]，运输是[2，3，2，4]，那么totalCosts将是{3，8，4，7}，并且将被排序为{3，4，7，8}。我希望重新排序成本和运费，使其与总额相对应，因此成本为[1，2，3，5]，运费为[2，2，4，3]。

Answer 1

这里有一个不使用映射的解决方案。相反，我们有一个自定义比较器，它使用成本和运费的总和来对数组位置进行排序。然后，我们创建新的数组，并从旧数组中排序的位置中拾取值。

public static void main(String[] args) {
int n = 4;
int[] costs = {1, 5, 2, 3};
int[] shipping = {2, 3, 2, 4};
Integer[] totals = new Integer[n];
for(int i = 0; i < n; ++i) {
totals[i] = i;
}
Arrays.sort(totals, Comparator.comparingInt(k -> (costs[k] + shipping[k])));
int[] newCosts = new int[n];
int[] newShipping = new int[n];
for(int i = 0; i < n; ++i) {
newCosts[i] = costs[totals[i]];
newShipping[i] = shipping[totals[i]];
}
for(int i = 0; i < n; ++i){
System.out.println((i + 1) + ": Cost=" + newCosts[i] + ", Shipping=" + newShipping[i] + ", Total=" + (newCosts[i] + newShipping[i]));
}
}

解释

totals数组包含从0到n(示例中为4(的索引列表。Arrays.sort()使用比较器对索引进行排序，在给定索引的情况下，比较器提取该位置的总数。排序后，totals数组将按顺序列出成本和运输总额的索引。

之后，我们可以使用排序后的索引创建新的成本和运输数组。

编辑

根据ttzn在评论中的建议，您可以将代码压缩为：

public static void main(String[] args) {
int n = 4;
int[] costs = {1, 5, 2, 3};
int[] shipping = {2, 3, 2, 4};
int[] totals = IntStream.range(0, n).boxed().sorted(Comparator.comparingInt(k -> (costs[(int)k] + shipping[(int)k]))).mapToInt(Integer::intValue).toArray();
int[] newCosts = IntStream.of(totals).map(i -> costs[i]).toArray();
int[] newShipping = IntStream.of(totals).map(i -> shipping[i]).toArray();
for (int i = 0; i < n; ++i) {
System.out.println((i + 1) + ": Cost=" + newCosts[i] + ", Shipping=" + newShipping[i] + ", Total=" + (newCosts[i] + newShipping[i]));
}
}

Answer 2

public List<Integer> sortPrices(int[] cost, int[] shipping) {
List<Integer> result = new ArrayList<>();
TreeMap<Integer, List<int[]>> map = new TreeMap<>();
int length = cost.length;
int[] origCost = new int[length];
int[] origShipping = new int[length];
for (int i = 0; i < length; i++) {
int price = cost[i] + shipping[i];
int[] arr = {i, i};
map.putIfAbsent(price, new ArrayList<>());
map.get(price).add(arr);
origCost[i] = cost[i];
origShipping[i] = shipping[i];
}
int j = 0;
for (int price : map.keySet()) {
for (int[] arr : map.get(price)) {
int ci = arr[0];
int si = arr[1];
cost[j] = origCost[ci];
shipping[j] = origShipping[si];
j++;
result.add(price);
}
}
return result;
}

Answer 3

我在python 中解决了问题

只要理解循环逻辑，你就可以做到。

for i in range(len(total)):
for j in range(len(total)):
if sorted_total[i]==total[j]:
new_costs[i]=costs[j]
new_shipping[i]=shipping[j]
print("i ",i)
print("j ",j)
break

Answer 4

这是一个不构建映射的基于流的解决方案。

1. 建立一个Stream<int[]>，在int[]数组中存储一个总数和索引

2. 流使用这些数组的自定义比较器进行排序(首先按总数，然后按索引(

3. 有意将peek与AtomicInteger一起用于对输入costs和ships阵列进行重新排序
   注意：然而，这可以被视为"；滥用；由于流外部数据的副作用更新而加剧

4. 生成并返回合计数组。

public static int[] getTotals(int[] costs, int[] ships) {
assert costs.length == ships.length;
int[] copyCosts = Arrays.copyOf(costs, costs.length);
int[] copyShips = Arrays.copyOf(ships, ships.length);

AtomicInteger ix = new AtomicInteger(0);

return IntStream.range(0, costs.length)
.mapToObj(i -> new int[]{ costs[i] + ships[i], i })
.sorted(Comparator.<int[]>
comparingInt(p -> p[0])
.thenComparingInt(p -> p[1])
) // get sorted Stream<int[]>
.peek(p -> {
costs[ix.get()] = copyCosts[p[1]];
ships[ix.getAndIncrement()] = copyShips[p[1]];
})
.mapToInt(p -> p[0])
.toArray();
}