将具有重复元素的数组划分为具有唯一元素的数组
Partition an Array with duplicate elements into arrays with unique elements
我有一个结构如下的数组:
String Array = {"1","2","3","41","56","41","72","72","72","78","99"}
我想将这个数组分成多个值不重复的数组...像这样:
String Array1 = {"1","2","3","41","56","72","78","99"}
String Array2 = {"41","72"}
String Array3 = {"72"}
在 Java 中有没有直接的方法可以做到这一点,或者我必须用丑陋的循环来做到这一点(开玩笑!)?
谢谢!
UPDATE
我要让问题更难...现在我有一个结构如下所示的地图:
Map<String,String> map = new HashMap(){{
put("1@@96","10");
put("2@@100","5");
put("3@@23","100");
put("41@@34","14");
put("56@@22","25");
put("41@@12","100");
put("72@@10","100");
put("72@@100","120");
put("72@@21","0");
put("78@@22","7");
}}
请注意,值并不重要,但键很重要...
我该怎么做才能将此地图划分为子地图,例如:
Map map1 = {"1@@96" => "10"
"2@@100" => "5"
"3@@23" => "100"
"41@@34" => "14"
"56@@22" => "25"
"72@@10" => "100"
"78@@22" => "7"
}
Map map2 = {
"41@@12" => "100"
"72@@100" => "120"
}
Map map3 = {
"72@@100" => "120"
}
就像在地图的第一部分之前(在'@@'之前)是我希望唯一性所基于的ID......这就像数组示例一样,但有点困难和复杂...... .
抱歉中途更改了问题...
没有循环就做不到这一点。但是您可以使用集合来删除一些循环。您可以根据自己的喜好添加数据结构陷阱。
我在这里假设 bin 中元素的顺序必须与输入数组中元素的顺序一致。如果不是,这可以更有效地完成。
public static void main(String[] args) {
String[] array = { "1", "2", "3", "41", "56", "41", "72", "72", "72",
"78", "99" };
List<Set<String>> bins = new ArrayList<>();
for (String s : array) {
findOrCreateBin(bins, s).add(s);
}
System.out.println(bins); // Prints [[1, 2, 3, 41, 56, 72, 78, 99], [41, 72], [72]]
}
private static Set<String> findOrCreateBin(List<Set<String>> bins, String s) {
for (Set<String> bin : bins) {
if (!bin.contains(s)) {
return bin;
}
}
Set<String> bin = new LinkedHashSet<>();
bins.add(bin);
return bin;
}
库中可能没有任何内容(似乎不够通用)但有一些想法:
O(n) 时间和 O(n) space 复杂度。在这里,您只需计算每个数字出现的次数,然后将它们放入那么多的结果数组中。
@Edit:正如@mpkorstanje 指出的那样,如果在最坏的情况下将输入从数字更改为字符串或任何其他对象,这将降级为 O(n^2)。但是在那种情况下,您应该针对您正在处理的数据修改哈希恕我直言,因为它分布不均。
public List<List<Integer>> split(int[] input) {
Map<Integer, Integer> occurrences = new HashMap<>();
int maxOcc = 0;
for (int val : input) {
int occ = 0;
if (occurrences.containsKey(val)) {
occ = occurrences.get(val);
}
if (occ + 1 > maxOcc) {
maxOcc = occ + 1;
}
occurrences.put(val, occ + 1);
}
List<List<Integer>> result = new ArrayList<>(maxOcc);
for (int i = 0; i < maxOcc; i++) {
result.add(new LinkedList<>());
}
for (Map.Entry<Integer, Integer> entry : occurrences.entrySet()) {
for (int i = 0; i < entry.getValue(); i++) {
result.get(i).add(entry.getKey());
}
}
return result;
}
O(nlogn) 时间和 O(1) space 复杂度(不计算结果数组)但不保留顺序和 "destroys" 输入数组。在这里,您利用数组已经排序的事实,因此您可以遍历它并继续将元素添加到适当的结果列表中,具体取决于您查看的是重复条目还是 "new" 条目。
public List<List<Integer>> split(int[] input) {
Arrays.sort(input);
int maxDup = getMaxDuplicateNumber(input);
List<List<Integer>> result = new ArrayList<>(maxDup);
for(int i = 0; i < maxDup; i++) {
result.add(new LinkedList<>());
}
int count = 0;
result.get(0).add(input[0]);
for(int i = 1; i < input.length; i++) {
if(input[i] == input[i-1]) {
count++;
} else {
count = 0;
}
result.get(count).add(input[i]);
}
return result;
}
private int getMaxDuplicateNumber(int[] input) {
int maxDups = 1;
int currentDupCount = 1;
for(int i = 1; i < input.length; i++) {
if(input[i] == input[i - 1]) {
currentDupCount++;
} else {
currentDupCount = 1;
}
if(currentDupCount > maxDups) {
maxDups = currentDupCount;
}
}
return maxDups;
}
我有一个结构如下的数组:
String Array = {"1","2","3","41","56","41","72","72","72","78","99"}
我想将这个数组分成多个值不重复的数组...像这样:
String Array1 = {"1","2","3","41","56","72","78","99"}
String Array2 = {"41","72"}
String Array3 = {"72"}
在 Java 中有没有直接的方法可以做到这一点,或者我必须用丑陋的循环来做到这一点(开玩笑!)?
谢谢!
UPDATE
我要让问题更难...现在我有一个结构如下所示的地图:
Map<String,String> map = new HashMap(){{
put("1@@96","10");
put("2@@100","5");
put("3@@23","100");
put("41@@34","14");
put("56@@22","25");
put("41@@12","100");
put("72@@10","100");
put("72@@100","120");
put("72@@21","0");
put("78@@22","7");
}}
请注意,值并不重要,但键很重要... 我该怎么做才能将此地图划分为子地图,例如:
Map map1 = {"1@@96" => "10"
"2@@100" => "5"
"3@@23" => "100"
"41@@34" => "14"
"56@@22" => "25"
"72@@10" => "100"
"78@@22" => "7"
}
Map map2 = {
"41@@12" => "100"
"72@@100" => "120"
}
Map map3 = {
"72@@100" => "120"
}
就像在地图的第一部分之前(在'@@'之前)是我希望唯一性所基于的ID......这就像数组示例一样,但有点困难和复杂...... .
抱歉中途更改了问题...
没有循环就做不到这一点。但是您可以使用集合来删除一些循环。您可以根据自己的喜好添加数据结构陷阱。
我在这里假设 bin 中元素的顺序必须与输入数组中元素的顺序一致。如果不是,这可以更有效地完成。
public static void main(String[] args) {
String[] array = { "1", "2", "3", "41", "56", "41", "72", "72", "72",
"78", "99" };
List<Set<String>> bins = new ArrayList<>();
for (String s : array) {
findOrCreateBin(bins, s).add(s);
}
System.out.println(bins); // Prints [[1, 2, 3, 41, 56, 72, 78, 99], [41, 72], [72]]
}
private static Set<String> findOrCreateBin(List<Set<String>> bins, String s) {
for (Set<String> bin : bins) {
if (!bin.contains(s)) {
return bin;
}
}
Set<String> bin = new LinkedHashSet<>();
bins.add(bin);
return bin;
}
库中可能没有任何内容(似乎不够通用)但有一些想法:
O(n) 时间和 O(n) space 复杂度。在这里,您只需计算每个数字出现的次数,然后将它们放入那么多的结果数组中。
@Edit:正如@mpkorstanje 指出的那样,如果在最坏的情况下将输入从数字更改为字符串或任何其他对象,这将降级为 O(n^2)。但是在那种情况下,您应该针对您正在处理的数据修改哈希恕我直言,因为它分布不均。
public List<List<Integer>> split(int[] input) {
Map<Integer, Integer> occurrences = new HashMap<>();
int maxOcc = 0;
for (int val : input) {
int occ = 0;
if (occurrences.containsKey(val)) {
occ = occurrences.get(val);
}
if (occ + 1 > maxOcc) {
maxOcc = occ + 1;
}
occurrences.put(val, occ + 1);
}
List<List<Integer>> result = new ArrayList<>(maxOcc);
for (int i = 0; i < maxOcc; i++) {
result.add(new LinkedList<>());
}
for (Map.Entry<Integer, Integer> entry : occurrences.entrySet()) {
for (int i = 0; i < entry.getValue(); i++) {
result.get(i).add(entry.getKey());
}
}
return result;
}
O(nlogn) 时间和 O(1) space 复杂度(不计算结果数组)但不保留顺序和 "destroys" 输入数组。在这里,您利用数组已经排序的事实,因此您可以遍历它并继续将元素添加到适当的结果列表中,具体取决于您查看的是重复条目还是 "new" 条目。
public List<List<Integer>> split(int[] input) {
Arrays.sort(input);
int maxDup = getMaxDuplicateNumber(input);
List<List<Integer>> result = new ArrayList<>(maxDup);
for(int i = 0; i < maxDup; i++) {
result.add(new LinkedList<>());
}
int count = 0;
result.get(0).add(input[0]);
for(int i = 1; i < input.length; i++) {
if(input[i] == input[i-1]) {
count++;
} else {
count = 0;
}
result.get(count).add(input[i]);
}
return result;
}
private int getMaxDuplicateNumber(int[] input) {
int maxDups = 1;
int currentDupCount = 1;
for(int i = 1; i < input.length; i++) {
if(input[i] == input[i - 1]) {
currentDupCount++;
} else {
currentDupCount = 1;
}
if(currentDupCount > maxDups) {
maxDups = currentDupCount;
}
}
return maxDups;
}