如何在 Java 中创建关联数组结构并排序，同时保留具有不同值对的重复键
How in Java do I create an associative array structure and sorted, while keeping duplicate keys with different values pairs
存在两个逗号分隔的字符串。
第一个字符串本质上是键，第二个是链接值，
第一个字符串需要按升序排列，同时保留任何重复值，第二个字符串需要按顺序排列以保持顺序不变。
到目前为止，查看哈希图和元组都没有成功。
系统是Java 6
String A = "3, 4, 1, 2, 3"
String B = "19, 24, 32, 68, 50"
需要结果输出
String A = "1, 2, 3, 3, 4"
String B = "32, 68, 19, 50, 24"
您有多种可能性来实现您的要求。这里有两个示例（在示例代码中并行存在）：
- 您可以使用
Map<Integer, List<Integer>> 来保存一个键及其在 List 中的所有值
- 您可以创建一个只包含一个键和一个值的 POJO class，但是您需要创建它 sortable/comparable 并使用合适的数据结构
看到这个例子，注意代码注释：
public class WhosebugMain {
public static void main(String[] args) {
String a = "3, 4, 1, 2, 3";
String b = "19, 24, 32, 68, 50";
// Map-approach: use a map that maps a key to a list of values
Map<Integer, List<Integer>> ab = new TreeMap<>();
// Pair-approach: make a sortable POJO that holds a key and a value only
// and create a data structure that holds them sorted
SortedSet<Pair> pairList = new TreeSet<Pair>();
// split both Strings by comma
String[] aSplit = a.split(",");
String[] bSplit = b.split(",");
// check if the length of the resulting arrays is the same
if (aSplit.length == bSplit.length) {
// if yes, go through the arrays of numbers
for (int i = 0; i < aSplit.length; i++) {
int key = Integer.parseInt(aSplit[i].trim());
int value = Integer.parseInt(bSplit[i].trim());
// in the Pair-approach, you just have to create a Pair with the value found
Pair pair = new Pair(key, value);
// and add it to the set of pairs
pairList.add(pair);
// the following check is only needed for the Map-solution
if (ab.containsKey(key)) {
// if the key is already present,
// just add the new value to its value list
ab.get(key).add(value);
// sort the value list each time a new value has been added
ab.get(key).sort(Comparator.naturalOrder());
} else {
// if the key is not present in the Map so far,
// create a new List for the value
List<Integer> valueList = new ArrayList<>();
// add the value to that list
valueList.add(value);
// and put both into the Map
ab.put(key, valueList);
}
}
} else {
System.err.println("The Strings have different amounts of elements!");
}
// print what's in the Map
System.out.println("Map-approach:");
for (int key : ab.keySet()) {
List<Integer> value = ab.get(key);
for (int val : value) {
System.out.println(key + " : " + val);
}
}
System.out.println("————————————————");
System.out.println("Pairs-approach:");
for (Pair pair : pairList) {
System.out.println(pair.key + " : " + pair.val);
}
}
/**
* This class is needed for the Pair-approach.
* It is comparable (and by that, sortable) and will be sorted by key
* and if the keys are equal, it will sort by value.
*/
static class Pair implements Comparable<Pair> {
int key;
int val;
Pair(int key, int value) {
this.key = key;
this.val = value;
}
@Override
public int compareTo(Pair otherPair) {
if (key == otherPair.key) {
if (val == otherPair.val) {
return 0;
} else if (val < otherPair.key) {
return -1;
} else {
return 1;
}
} else if (key < otherPair.key) {
return -1;
} else {
return 1;
}
}
}
}
此代码产生以下输出：
Map-approach:
1 : [32]
2 : [68]
3 : [19, 50]
4 : [24]
————————————————
Pairs-approach:
1 : 32
2 : 68
3 : 19
3 : 50
4 : 24
编辑
由于 Pair-方法不能正确排序，我想出了这个 Map-方法：
public class WhosebugMain {
public static void main(String[] args) {
String a = "3, 4, 1, 3, 3, 2, 3";
String b = "5, 24, 35, 99, 32, 68, 19";
// Map-approach: use a map that maps a key to a list of values
Map<Integer, List<Integer>> ab = new TreeMap<>();
// split both Strings by comma
String[] aSplit = a.split(",");
String[] bSplit = b.split(",");
// check if the length of the resulting arrays is the same
if (aSplit.length == bSplit.length) {
// if yes, go through the arrays of numbers
for (int i = 0; i < aSplit.length; i++) {
int key = Integer.parseInt(aSplit[i].trim());
int value = Integer.parseInt(bSplit[i].trim());
// the following check is only needed for the Map-solution
if (ab.containsKey(key)) {
// if the key is already present, just add the new value to its value list
ab.get(key).add(value);
// sort the value list each time a new value has been added
ab.get(key).sort(Comparator.naturalOrder());
} else {
// if the key is not present in the Map so far, create a new List for the value
List<Integer> valueList = new ArrayList<>();
// add the value to that list
valueList.add(value);
// and put both into the Map
ab.put(key, valueList);
}
}
} else {
System.err.println("The Strings have different amounts of elements!");
}
// print what's in the Map
System.out.println("Map-approach:");
for (int key : ab.keySet()) {
List<Integer> value = ab.get(key);
for (int val : value) {
System.out.println(key + " : " + val);
}
}
}
}
它更短并且使用 Map<Integer, List<Integer>> 并在每次添加新值时对 List<Integer> 进行排序（第一个值除外，它不需要排序）。这需要输出代码中的另一个循环，但您不必创建新的 class.
它产生以下输出：
Map-approach:
1 : 35
2 : 68
3 : 5
3 : 19
3 : 32
3 : 99
4 : 24
第一：java6太老了；至少 java 8（通用类型，表达流）。然后使用以小写字母开头的变量和方法名称，因为这是一个非常严格的社区约定。
在 java 6 中，一个 糟糕的 解决方案将是一个压缩长数组：
- 必须对成对的 A 和 B 值进行排序，因此这里的值是打包的。
- 想要订购的东西意味着 get 的对数访问时间，
因此对排序数组进行二分查找是可行的。
- 使用数组的结果是固定的数组大小：insert/delete很麻烦；
一个 List 会更好，一个 Map 然后最好。
将字符串转化为单个元素的数据
public class MapIntToInts {
long[] ab;
public MapIntToInts (String A, String B) {
String[] a = A.split(", ");
String[] b = B.split(", ");
ab = new int[a.length];
for (int i = 0; i < ab.length; ++i) {
long key = Integer.parseInt(a[i]) << 32L;
long value = Integer.parseInt(b[i]) && 0xFFFF_FFFFL;
ab[i] = key | value;
}
Arrays.sort(ab);
}
获取一个A键的值可以通过二分查找在O(log N)时间完成:
public int[] get(int key) {
long abKey <<= 32L;
int firstI = Arrays.binSearch(ab, key);
if (firstI < 0) { // Not found
firstI = ~firstI ; // Insert position
}
int i = firstI;
while (i < ab.length && ab[i] >> 32 == key) {
++i;
}
int n = i - firstI;
int[] result = new int[n];
for (int i = 0; i < n; ++i) {
result[i] = (int)ab[firstI + i];
}
Arrays.sort(result); // For mixed negative positive values
return result();
}
}
用法：
String A = "3, 4, 1, 2, 3";
String B = "19, 24, 32, 68, 50";
MapIntToInts map = MapIntToInts(A, B);
int[] results = map.get(3);
改进：
- 将
long[] ab; 替换为 int[] a; int[b]; 或更好：
- 将
long[] ab; 替换为 int[] uniqueKeys; int[][] values;。
您应该投入更多精力将问题分解成更小的块。例如，将字符串转换为整数数组是一个比标题中声明的操作简单得多的操作。假设它可以单独处理。
Integer[] A = {3, 4, 1, 2, 3};
Integer[] B = {19, 24, 32, 68, 50};
因此，当您有两个整数数组供您使用时，您可以受益于自然排序——如果您选择SortedMap 解决方案。
SortedMap<Integer, List<Integer>> map = new TreeMap<Integer, List<Integer>>();
for (int i = 0; i < A.length; i++) {
if (map.get(A[i]) == null) {
List<Integer> list = new ArrayList<Integer>();
list.add(B[i]);
map.put(A[i], list);
} else {
map.get(A[i]).add(B[i]);
}
}
上面提到的最复杂的事情就是在创建输出时去掉结尾的逗号。但是用一个小技巧应该不是问题。
StringBuilder sb = new StringBuilder();
for (List<Integer> list : map.values()) {
for (Integer integer : list) {
sb.append(", ").append(integer);
}
}
String output = sb.toString().substring(2);
如果您想验证答案，您可以通过在应用程序启动时将 -ea 参数传递给 JVM 来启用断言（或者只编写一个单元测试）。
assert output.equals("32, 68, 19, 50, 24");
存在两个逗号分隔的字符串。
第一个字符串本质上是键，第二个是链接值，
第一个字符串需要按升序排列，同时保留任何重复值，第二个字符串需要按顺序排列以保持顺序不变。
到目前为止，查看哈希图和元组都没有成功。 系统是Java 6
String A = "3, 4, 1, 2, 3"
String B = "19, 24, 32, 68, 50"
需要结果输出
String A = "1, 2, 3, 3, 4"
String B = "32, 68, 19, 50, 24"
您有多种可能性来实现您的要求。这里有两个示例（在示例代码中并行存在）：
- 您可以使用
Map<Integer, List<Integer>>来保存一个键及其在List 中的所有值
- 您可以创建一个只包含一个键和一个值的 POJO class，但是您需要创建它 sortable/comparable 并使用合适的数据结构
看到这个例子，注意代码注释：
public class WhosebugMain {
public static void main(String[] args) {
String a = "3, 4, 1, 2, 3";
String b = "19, 24, 32, 68, 50";
// Map-approach: use a map that maps a key to a list of values
Map<Integer, List<Integer>> ab = new TreeMap<>();
// Pair-approach: make a sortable POJO that holds a key and a value only
// and create a data structure that holds them sorted
SortedSet<Pair> pairList = new TreeSet<Pair>();
// split both Strings by comma
String[] aSplit = a.split(",");
String[] bSplit = b.split(",");
// check if the length of the resulting arrays is the same
if (aSplit.length == bSplit.length) {
// if yes, go through the arrays of numbers
for (int i = 0; i < aSplit.length; i++) {
int key = Integer.parseInt(aSplit[i].trim());
int value = Integer.parseInt(bSplit[i].trim());
// in the Pair-approach, you just have to create a Pair with the value found
Pair pair = new Pair(key, value);
// and add it to the set of pairs
pairList.add(pair);
// the following check is only needed for the Map-solution
if (ab.containsKey(key)) {
// if the key is already present,
// just add the new value to its value list
ab.get(key).add(value);
// sort the value list each time a new value has been added
ab.get(key).sort(Comparator.naturalOrder());
} else {
// if the key is not present in the Map so far,
// create a new List for the value
List<Integer> valueList = new ArrayList<>();
// add the value to that list
valueList.add(value);
// and put both into the Map
ab.put(key, valueList);
}
}
} else {
System.err.println("The Strings have different amounts of elements!");
}
// print what's in the Map
System.out.println("Map-approach:");
for (int key : ab.keySet()) {
List<Integer> value = ab.get(key);
for (int val : value) {
System.out.println(key + " : " + val);
}
}
System.out.println("————————————————");
System.out.println("Pairs-approach:");
for (Pair pair : pairList) {
System.out.println(pair.key + " : " + pair.val);
}
}
/**
* This class is needed for the Pair-approach.
* It is comparable (and by that, sortable) and will be sorted by key
* and if the keys are equal, it will sort by value.
*/
static class Pair implements Comparable<Pair> {
int key;
int val;
Pair(int key, int value) {
this.key = key;
this.val = value;
}
@Override
public int compareTo(Pair otherPair) {
if (key == otherPair.key) {
if (val == otherPair.val) {
return 0;
} else if (val < otherPair.key) {
return -1;
} else {
return 1;
}
} else if (key < otherPair.key) {
return -1;
} else {
return 1;
}
}
}
}
此代码产生以下输出：
Map-approach:
1 : [32]
2 : [68]
3 : [19, 50]
4 : [24]
————————————————
Pairs-approach:
1 : 32
2 : 68
3 : 19
3 : 50
4 : 24
编辑
由于 Pair-方法不能正确排序，我想出了这个 Map-方法：
public class WhosebugMain {
public static void main(String[] args) {
String a = "3, 4, 1, 3, 3, 2, 3";
String b = "5, 24, 35, 99, 32, 68, 19";
// Map-approach: use a map that maps a key to a list of values
Map<Integer, List<Integer>> ab = new TreeMap<>();
// split both Strings by comma
String[] aSplit = a.split(",");
String[] bSplit = b.split(",");
// check if the length of the resulting arrays is the same
if (aSplit.length == bSplit.length) {
// if yes, go through the arrays of numbers
for (int i = 0; i < aSplit.length; i++) {
int key = Integer.parseInt(aSplit[i].trim());
int value = Integer.parseInt(bSplit[i].trim());
// the following check is only needed for the Map-solution
if (ab.containsKey(key)) {
// if the key is already present, just add the new value to its value list
ab.get(key).add(value);
// sort the value list each time a new value has been added
ab.get(key).sort(Comparator.naturalOrder());
} else {
// if the key is not present in the Map so far, create a new List for the value
List<Integer> valueList = new ArrayList<>();
// add the value to that list
valueList.add(value);
// and put both into the Map
ab.put(key, valueList);
}
}
} else {
System.err.println("The Strings have different amounts of elements!");
}
// print what's in the Map
System.out.println("Map-approach:");
for (int key : ab.keySet()) {
List<Integer> value = ab.get(key);
for (int val : value) {
System.out.println(key + " : " + val);
}
}
}
}
它更短并且使用 Map<Integer, List<Integer>> 并在每次添加新值时对 List<Integer> 进行排序（第一个值除外，它不需要排序）。这需要输出代码中的另一个循环，但您不必创建新的 class.
它产生以下输出：
Map-approach:
1 : 35
2 : 68
3 : 5
3 : 19
3 : 32
3 : 99
4 : 24
第一：java6太老了；至少 java 8（通用类型，表达流）。然后使用以小写字母开头的变量和方法名称，因为这是一个非常严格的社区约定。
在 java 6 中，一个 糟糕的 解决方案将是一个压缩长数组：
- 必须对成对的 A 和 B 值进行排序，因此这里的值是打包的。
- 想要订购的东西意味着 get 的对数访问时间， 因此对排序数组进行二分查找是可行的。
- 使用数组的结果是固定的数组大小：insert/delete很麻烦； 一个 List 会更好，一个 Map 然后最好。
将字符串转化为单个元素的数据
public class MapIntToInts {
long[] ab;
public MapIntToInts (String A, String B) {
String[] a = A.split(", ");
String[] b = B.split(", ");
ab = new int[a.length];
for (int i = 0; i < ab.length; ++i) {
long key = Integer.parseInt(a[i]) << 32L;
long value = Integer.parseInt(b[i]) && 0xFFFF_FFFFL;
ab[i] = key | value;
}
Arrays.sort(ab);
}
获取一个A键的值可以通过二分查找在O(log N)时间完成:
public int[] get(int key) {
long abKey <<= 32L;
int firstI = Arrays.binSearch(ab, key);
if (firstI < 0) { // Not found
firstI = ~firstI ; // Insert position
}
int i = firstI;
while (i < ab.length && ab[i] >> 32 == key) {
++i;
}
int n = i - firstI;
int[] result = new int[n];
for (int i = 0; i < n; ++i) {
result[i] = (int)ab[firstI + i];
}
Arrays.sort(result); // For mixed negative positive values
return result();
}
}
用法：
String A = "3, 4, 1, 2, 3";
String B = "19, 24, 32, 68, 50";
MapIntToInts map = MapIntToInts(A, B);
int[] results = map.get(3);
改进：
- 将
long[] ab;替换为int[] a; int[b];或更好： - 将
long[] ab;替换为int[] uniqueKeys; int[][] values;。
您应该投入更多精力将问题分解成更小的块。例如，将字符串转换为整数数组是一个比标题中声明的操作简单得多的操作。假设它可以单独处理。
Integer[] A = {3, 4, 1, 2, 3};
Integer[] B = {19, 24, 32, 68, 50};
因此，当您有两个整数数组供您使用时，您可以受益于自然排序——如果您选择SortedMap 解决方案。
SortedMap<Integer, List<Integer>> map = new TreeMap<Integer, List<Integer>>();
for (int i = 0; i < A.length; i++) {
if (map.get(A[i]) == null) {
List<Integer> list = new ArrayList<Integer>();
list.add(B[i]);
map.put(A[i], list);
} else {
map.get(A[i]).add(B[i]);
}
}
上面提到的最复杂的事情就是在创建输出时去掉结尾的逗号。但是用一个小技巧应该不是问题。
StringBuilder sb = new StringBuilder();
for (List<Integer> list : map.values()) {
for (Integer integer : list) {
sb.append(", ").append(integer);
}
}
String output = sb.toString().substring(2);
如果您想验证答案，您可以通过在应用程序启动时将 -ea 参数传递给 JVM 来启用断言（或者只编写一个单元测试）。
assert output.equals("32, 68, 19, 50, 24");