java - 按每个数字及其索引的乘积对整数数组进行排序？‽

Question

我正在做以下编程练习：按值和索引对数组进行排序。声明是：

您的任务是通过值和位置索引的乘积对整数数组进行排序。

对于排序，索引从 1 开始，而不是从 0！排序必须是升序的。该数组永远不会为空，并且始终包含数字。

例子：

输入：23、2、3、4、5 值和指数的乘积：23 => 23 * 1 = 23 -> Output-Pos 4 2 => 2 * 2 = 4 -> Output-Pos 1 3 => 3 * 3 = 9 -> 输出位置 2 4 => 4 * 4 = 16 -> 输出位置 3 5 => 5 * 5 = 25 -> 输出位置 5

输出：2、3、4、23、5

我尝试使用一个映射，我们将原始数组的值存储为键，原始数组与其索引的乘积是值：

import java.util.*;
import java.util.stream.*;
public class Kata
{
  public static int[] sortByValueAndIndex/**/(int[] array)
  {
    System.out.println("\nArray: "+Arrays.toString(array));
    Map<Integer,Integer> map = new HashMap<Integer,Integer>();
    for(int i = 0; i < array.length; i++){
      map.put(array[i],array[i]*(i+1));
    }
    System.out.println("map: "+map.toString());
    map = map.entrySet().stream().sorted(Map.Entry.comparingByValue())
          .collect(Collectors.toMap(Map.Entry::getKey, Map.Entry::getValue,
          (e1, e2) -> e1, LinkedHashMap::new));
    System.out.println("sorted map: "+map.toString());          
    return map.keySet().stream().mapToInt(Number::intValue).toArray();
  }
}

它适用于具有唯一元素的数组，例如以下测试（从练习中提取）：

import org.junit.Test;
import static org.junit.Assert.assertEquals;
import org.junit.runners.JUnit4;
import java.util.Arrays;

public class KataTests {
    @Test
    public void exampleTests() {

      int[] actual = Kata.sortByValueAndIndex(new int[] { 1, 2, 3, 4, 5 });
      int[] expected = new int[] { 1, 2, 3, 4, 5 };
      String message = "Your result:\n" + arrayToString(actual) + "\n\nExpected result:\n" + arrayToString(expected) + "\n\n";
      assertEquals(message, arrayToString(expected), arrayToString(actual));

      actual = Kata.sortByValueAndIndex(new int[] { 23, 2, 3, 4, 5 });
      expected = new int[] { 2, 3, 4, 23, 5 };
      message = "Your result:\n" + arrayToString(actual) + "\n\nExpected result:\n" + arrayToString(expected) + "\n\n";
      assertEquals(message, arrayToString(expected), arrayToString(actual));

      actual = Kata.sortByValueAndIndex(new int[] { 26, 2, 3, 4, 5 });
      expected = new int[] { 2, 3, 4, 5, 26 };
      message = "Your result:\n" + arrayToString(actual) + "\n\nExpected result:\n" + arrayToString(expected) + "\n\n";
      assertEquals(message, arrayToString(expected), arrayToString(actual));

      actual = Kata.sortByValueAndIndex(new int[] { 9, 5, 1, 4, 3 });
      expected = new int[] { 1, 9, 5, 3, 4 };
      message = "Your result:\n" + arrayToString(actual) + "\n\nExpected result:\n" + arrayToString(expected) + "\n\n";
      assertEquals(message, arrayToString(expected), arrayToString(actual));
    }

    private String arrayToString(int[] array)
    {
      return Arrays.toString(array);
    }
}

然而，当我们输入一个包含重复元素的数组时，它会引发异常，因为 map 的键是唯一的，所以我们省略了一些原始数组的数字。

例如，如果输入是：

[7, -9, 24, 0, 7, 23, -4, -28, -14, 5, 20, 26, 22, -24]

电流输出：

[-24, -28, -14, -4, -9, 0, 7, 5, 24, 23, 20, 22, 26]

预期之一：

[-24, -28, -14, -4, -9, 0, 7, 7, 5, 24, 23, 20, 22, 26]

正如我们所看到的，使用跟踪，我们观察到地图只包含最后 7 个的乘积，7*5=35：

Array: [7, -9, 24, 0, 7, 23, -4, -28, -14, 5, 20, 26, 22, -24]

map: {0=0, -4=-28, 5=50, 7=35, -9=-18, -14=-126, 20=220, 22=286, 23=138, -24=-336, 24=72, 26=312, -28=-224}

sorted map: {-24=-336, -28=-224, -14=-126, -4=-28, -9=-18, 0=0, 7=35, 5=50, 24=72, 23=138, 20=220, 22=286, 26=312}

有没有办法解决这种行为以允许重复元素？我们是否需要使用地图以外的其他数据结构？有没有其他方法，比如比较器/比较，或者只是使用列表/数组？‽</p>

我也读过：

• 自定义排序java数组
• 使用 Lambda 表达式，我想使用 Java 语言按整数值排序
• Java 8 Stream 和数组操作
• 在 HashMap 中存储一个数组
• 按值对 Map<Key, Value> 进行排序
• 从 Java 中的 HashMap 获取密钥
• 如何将 Java HashSet<Integer> 转换为原始 int 数组？
• Java Sorting：按属性对对象数组进行排序，对象不允许使用Comparable
• 如何在 Java 中正确覆盖 toString()？

编辑：正如@JB Nizet 建议的那样，我们可以执行以下操作：

import java.util.*;
import java.util.stream.*;
public class Kata
{
  public static int[] sortByValueAndIndex/**/(int[] array)
  {
    ElementWithProduct[] elements = new ElementWithProduct[array.length];
    for(int i = 0; i < elements.length; i++){
      elements[i] = new ElementWithProduct(array[i], array[i]*(i+1));
    }
    Arrays.sort(elements, new Comparator<ElementWithProduct>(){
      public int compare(ElementWithProduct e1, ElementWithProduct e2){
        if(e1.product > e2.product){
          return 1;
        }
        if(e1.product < e2.product){
          return -1;
        }
        return 0;
      }
    });
    for(int i = 0; i < elements.length; i++){
      array[i] = elements[i].value;
    }
    return array;
  }

  public static class ElementWithProduct{
    public int value;
    public int product;

    public ElementWithProduct(int value, int product){
      this.value = value;
      this.product = product;
    }
  }
}

标签： javaarrayssortingfor-loopindexing

Answer 1

创建一个List<ElementWithProduct>（或类型为 的数组ElementWithProduct[]），其中包含包含元素值的对象，以及它的值和它的索引的乘积。

然后按产品对该列表或数组进行排序。

然后将其转换回元素数组。