我有一项服务来查找旅程并删除重复的访问城市。
public static void main(String[] args){
List<List<String>> allPaths = new ArrayList<>();
allPaths.add(List.of("Newyork","Washington","Los Angeles","Chicago"));
allPaths.add(List.of("Newyork","Washington","Houston"));
allPaths.add(List.of("Newyork","Dallas"));
allPaths.add(List.of("Newyork","Columbus", "Chicago"));
Set<String> orphanageLocations = new HashSet<>();
removeDuplicatedLocation(allPaths, orphanageLocations);
//expected allPaths:
//"Newyork","Washington","Los Angeles","Chicago"
//"Newyork","Dallas"
//"Newyork","Columbus"
//expected orphanageLocations
//"Houston"
}
private static void removeDuplicatedLocation(List<List<String>> allPaths, Set<String> orphanageLocations){
//do something here
}
在i 中存储从 a到其他城市allPaths的所有路径。origin但可能某些路径将包含相同的城市，例如Washington出现在第一条和第二条路径中。
现在我需要一项服务来删除那个重复的城市。当两条路径具有相同的城市时，我们会选择去更多城市的路径。
并且服务还返回无法访问的城市。例如，第二条路径有“华盛顿”与第一条路径重复，然后我们删除第二条路径（它的城市比第一条路径少），然后没有可用的“休斯顿”路径 -> 成为孤儿院
其他测试用例：
public static void main(String[] args){
List<List<String>> allPaths = new ArrayList<>();
allPaths.add(List.of("Newyork","Washington","Los Angeles","Chicago", "Dallas"));
allPaths.add(List.of("Newyork","Los Angeles","Houston", "Philadenphia"));
allPaths.add(List.of("Newyork","Dallas"));
allPaths.add(List.of("Newyork","Columbus", "San Francisco"));
Set<String> orphanageLocations = new HashSet<>();
removeDuplicatedLocation(allPaths, orphanageLocations);
//expected allPaths:
//"Newyork","Washington","Los Angeles","Chicago", "Dallas"
//"Newyork","Columbus", "San Francisco"
//expected orphanageLocations
//"Houston","Philadenphia"
}
有人会建议我一个算法来解决它吗？
---编辑1：我在这里更新了我的肮脏解决方案，仍在等待更好的解决方案
private static void removeDuplicatedLocation(List<List<String>> allPaths, Set<String> orphanageLocations){
//sort to make sure the longest path is on top
List<List<String>> sortedPaths = allPaths.stream().sorted((a, b) -> Integer.compare(b.size(), a.size()))
.collect(Collectors.toList());
for(int i = 0; i < sortedPaths.size()-1; i++){
List<String> path = sortedPaths.get(i);
orphanageLocations.removeIf(path::contains);
for(int j = i+1; j < sortedPaths.size(); j++){
for(int k = 1; k < path.size();k++) {
Iterator<String> iterator = sortedPaths.get(j).iterator();
boolean isRemove = false;
while (iterator.hasNext()) {
String city = iterator.next();
if(isRemove && !path.contains(city)){
orphanageLocations.add(city);
}
if(StringUtils.equals(city, path.get(k))){
isRemove = true;
}
if(isRemove){
iterator.remove();
}
}
}
}
}
//remove path if it's only origin
sortedPaths.removeIf(item -> item.size() == 1);
allPaths.clear();
allPaths.addAll(sortedPaths);
}
---编辑2：感谢@devReddit 的解决方案，我做了一个包含大量路线的小测试。每条路径中的城市越多，您的解决方案就越慢
public static void main(String[] args){
List<List<String>> allPaths = new ArrayList<>();
List<List<String>> allPaths2 = new ArrayList<>();
List<String> locations = Stream.of("A", "B", "C", "D", "E", "F", "G", "H", "I", "J", "K", "L", "M", "N",
"O", "P", "Q", "R", "S", "T", "U", "V", "X", "Y", "Z").collect(Collectors.toList());
Random rand = new Random();
int numberOfRoute = 10000;
String origin = "NY";
for(int i = 0; i < numberOfRoute; i++){
List<String> route = new ArrayList<>();
List<String> route2 = new ArrayList<>();
route.add(origin);
route2.add(origin);
//int routeLength = rand.nextInt(locations.size());
int routeLength = 10;
while(route.size() < routeLength){
int randomIndex = rand.nextInt(locations.size()-1);
if(!route.contains(locations.get(randomIndex))){
route.add(locations.get(randomIndex));
route2.add(locations.get(randomIndex));
}
}
allPaths.add(route);
allPaths2.add(route2);
}
System.out.println("Process for " + allPaths2.size() + " routes");
Set<String> orphanageLocations2 = new HashSet<>();
long startTime2 = System.currentTimeMillis();
removeDuplicatedLocation3(allPaths2, orphanageLocations2); //uncle bob solution
long endTime2 = System.currentTimeMillis();
System.out.println(allPaths2);
System.out.println(orphanageLocations2);
System.out.println("Total time uncleBob solution(ms):" + (endTime2-startTime2));
System.out.println("Process for " + allPaths.size() + " routes");
Set<String> orphanageLocations = new HashSet<>();
long startTime = System.currentTimeMillis();
removeDuplicatedLocation(allPaths, orphanageLocations); //devReddit solution
long endTime = System.currentTimeMillis();
System.out.println(allPaths);
System.out.println(orphanageLocations);
System.out.println("Total time devReddit solution(ms):" + (endTime-startTime));
}
//devReddit solution
private static void removeDuplicatedLocation(List<List<String>> allPaths, Set<String> orphanageLocations) {
List<List<String>> sortedFixedPaths = allPaths // List.of produces immutable lists,
.stream() // so you can't directly remove string from the list
.sorted((a, b) -> Integer.compare(b.size(), a.size())) // this fixed list will be needed later
.collect(Collectors.toList());
List<List<String>> sortedPaths = sortedFixedPaths // The list is regenerated through manual deep copy
.stream() // generated a single string from the streams of
.map(path -> // each List<String> and created new list, this is now mutable
new ArrayList<>(Arrays.asList(String.join(",", path).split(","))))
.collect(Collectors.toList());
Set<List<String>> valuesToBeRemoved = new HashSet<>();
String source = sortedPaths.get(0).get(0);
Map<String, List<Integer>> cityMapOfIndex = generateHashMap(sortedPaths, source); // This hashmap keeps track of the existence of cities in different lists
removeDuplicates(cityMapOfIndex, sortedPaths); // this method removes the duplicates from the smaller paths
// adds the remaining cities to orphanList
cityMapOfIndex.forEach((cityName, value) -> { // this block checks whether any mid element in the path is gone
int index = value.get(0); // removes the path from result list
List<String> list = sortedPaths.get(index);
int indexInPath = list.indexOf(cityName);
if (indexInPath != sortedFixedPaths.get(index).indexOf(cityName)) {
orphanageLocations.add(cityName);
sortedPaths.get(index).remove(indexInPath);
}
});
valuesToBeRemoved.add(new ArrayList<>(Collections.singleton(source))); // To handle the case where only source remains in the path
sortedPaths.removeAll(valuesToBeRemoved); // after removing other duplicates
allPaths.clear();
allPaths.addAll(sortedPaths);
}
private static void removeDuplicates(Map<String, List<Integer>> cityMapOfIndex, List<List<String>> sortedPaths) {
for (Map.Entry<String, List<Integer>> entry : cityMapOfIndex.entrySet()) {
List<Integer> indexList = entry.getValue();
while (indexList.size() > 1) {
int index = indexList.get(indexList.size() - 1); // get the last index i.e. the smallest list of city where this entry exists
sortedPaths.get(index).remove(entry.getKey()); // remove the city from the list
indexList.remove((Integer) index); // update the index list of occurrence
}
cityMapOfIndex.put(entry.getKey(), indexList);
}
}
private static Map<String, List<Integer>> generateHashMap(List<List<String>> sortedPaths,
String source) {
Map<String, List<Integer>> cityMapOfIndex = new HashMap<>();
for (int x = 0; x < sortedPaths.size(); x++) {
int finalX = x;
sortedPaths.get(x)
.forEach(city -> {
if (!city.equalsIgnoreCase(source)) { // add entries for all except the source
List<Integer> indexList = cityMapOfIndex.containsKey(city) ? // checks whether there's already an entry
cityMapOfIndex.get(city) : new ArrayList<>(); // to avoid data loss due to overwriting
indexList.add(finalX); // adds the index of the List of string
cityMapOfIndex.put(city, indexList); // add or update the map with current indexList
}
});
}
return cityMapOfIndex;
}
//Bob solution
private static void removeDuplicatedLocation3(List<List<String>> allPaths, Set<String> orphanageLocations){
//sort to make sure the longest path is on top
List<List<String>> sortedPaths = allPaths.stream().sorted((a, b) -> Integer.compare(b.size(), a.size()))
.collect(Collectors.toList());
for(int i = 0; i < sortedPaths.size()-1; i++){
List<String> path = sortedPaths.get(i);
orphanageLocations.removeIf(path::contains);
for(int j = i+1; j < sortedPaths.size(); j++){
for(int k = 1; k < path.size();k++) {
Iterator<String> iterator = sortedPaths.get(j).iterator();
boolean isRemove = false;
while (iterator.hasNext()) {
String city = iterator.next();
if(isRemove && !path.contains(city)){
orphanageLocations.add(city);
}
if(StringUtils.equals(city, path.get(k))){
isRemove = true;
}
if(isRemove){
iterator.remove();
}
}
}
}
}
//remove path if it's only origin
sortedPaths.removeIf(item -> item.size() == 1);
allPaths.clear();
allPaths.addAll(sortedPaths);
}
这是结果之一：
路线长度为 6 的测试
Process for 10000 routes
[[NY, Q, Y, T, S, X], [NY, E], [NY, V, A, H, N], [NY, J, L, I], [NY, D], [NY, O], [NY, C], [NY, P, M], [NY, F], [NY, K], [NY, U], [NY, G], [NY, R], [NY, B]]
[]
Total time uncleBob solution(ms):326
Process for 10000 routes
[[NY, Q, Y, T, S, X], [NY, E], [NY, V], [NY, J, L], [NY, D], [NY, O]]
[A, B, C, F, G, H, I, K, M, N, P, R, U]
Total time devReddit solution(ms):206
路线长度为 10
Process for 10000 routes
[[NY, J, V, G, A, I, B, R, U, S], [NY, L, X, Q, M, E], [NY, K], [NY, Y], [NY, F, P], [NY, N], [NY, H, D], [NY, T, O], [NY, C]]
[]
Total time uncleBob solution(ms):292
Process for 10000 routes
[[NY, J, V, G, A, I, B, R, U, S]]
[C, D, E, F, H, K, L, M, N, O, P, Q, T, X, Y]
Total time devReddit solution(ms):471
结果也不一样，从同一个inpit，我的返回更有效的路线
实际上我这不是我所期望的，因为来自@devReddit 的解决方案看起来更好更快
谢谢