如何优化N个容器间重复元素去除算法以提升效率?
问题:多数组间去重,保留仅单数组存在的元素
我们有三个水果数组,每个数组内部元素无重复,但部分元素会在多个数组中出现。需要移除重复元素,让每个数组只保留仅在自身存在的唯一元素。
处理前:
arrayA = {"lychee", "orange", "grape", "watermelon"}; arrayB = {"banana", "grape", "pear", "apple"}; arrayC = {"pear", "orange", "strawberry", "apple"};
处理后:
arrayA = {"lychee", "watermelon"} arrayB = {"banana"} arrayC = {"strawberry"}
我已经写出了可运行的Java代码,但想找到更高效的算法,优化时间复杂度。
编辑说明:我简化了Java代码并添加了文档注释,现在寻求提升算法效率、降低时间复杂度的方案。
伪代码版本
declare method [@name=removeDuplicates] [@params={@name=NItems, @type=String-Matrix/Set-List}]: declare a variable [@name=MapList, @type=List[item:HashMap[key:String, value:Number]]] assign List.@new iterate NItems with @[index, element]: declare a variable [@name=nmap, @type=HashMap[key:String, value:Number]] assign HashMap.@new for each @[item] in @element, put [key:@item, value:0] to @[name=nmap] reference @[name=MapList][@index] to @[name=nmap] declare a variable [@name=result] with the same type of @NItems iterate NItems with @[index, element]: iterate MapList with @[mapIndex, mapElement] where @index != @mapIndex: iterate @element with @[item]: if @mapElement[@mapIndex] contains the [key:@item]: set the corresponding map @MapList[@index] update [key:@item, value:@old+1] set @result[@index] values: items from @MapList[@index] where it's value == 0 return @result
Java代码版本
/** * Remove duplicate items among N container * @param arrays list of item container, each container contains no duplicates, * and the container is unordered internally, which can be considered as a Set * @return N containers after remove duplicates */ @SuppressWarnings("unchecked") public static String[][] removeDuplicates(String[]... arrays) { Map<String, Integer>[] maps = new Map[arrays.length]; for (int i = 0; i < arrays.length; i++) { maps[i] = new HashMap<>(); for (String itm : arrays[i]) { maps[i].put(itm, 0); } } String[][] result = new String[arrays.length][]; for (int i = 0; i < arrays.length; i++) { for (int j = 0; j < maps.length; j++) { if (j == i) continue; for (String s : arrays[i]) { if (maps[j].containsKey(s)) maps[i].compute(s, (_, v) -> v + 1); } } int finalI = i; result[i] = Arrays.stream(arrays[i]) .filter(itm -> maps[finalI].get(itm) < 1) .toArray(String[]::new); } return result; }
内容的提问来源于stack exchange,提问作者Emiya Elien
相关产品推荐
相关产品推荐

