V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
LowBi
V2EX  ›  Java

不知道有没有更好的写法

  •  
  •   LowBi · 2021-04-09 00:06:50 +08:00 via Android · 2363 次点击
    这是一个创建于 1322 天前的主题,其中的信息可能已经有所发展或是发生改变。

    RT.个人项目上的一个问题,写了个例子,自己感觉写的方法较笨。😅

    https://www.wolai.com/beCZEzzoibLdm9yfrNrDCo

    ps:不过挺享受洗澡时在想代码怎么写,洗完立即把想到的写法敲出来😂

    8 条回复    2021-04-09 13:51:02 +08:00
    javapythongo
        1
    javapythongo  
       2021-04-09 00:18:17 +08:00
    你这个算法的时间复杂度是 O(m*n)了,而且在 if(x[i] == y[j])判定相等赋值后,应该直接 break 。
    可以先遍历 y 数组,存储在一个 set 集合中,再遍历 x 数组,原地修改即可,这样子的时间复杂度是 O(m+n)
    LGA1150
        2
    LGA1150  
       2021-04-09 00:19:24 +08:00
    int[] x = {1,2,3,4,5,6,7};
    int[] y = {2,4,7};
    int[] z = Arrays.stream(x).map(e -> Arrays.binarySearch(y, e) < 0 ? 0 : e).toArray();
    System.out.println(Arrays.toString(z));
    需要保证 y 有序
    LGA1150
        3
    LGA1150  
       2021-04-09 00:28:24 +08:00
    如果像 #1 说的使用集合并原地修改:
    Set<Integer> set = Arrays.stream(y).boxed().collect(Collectors.toSet());
    for (int i = 0; i < x.length; i++) {
    if (!set.contains(x[i])) x[i]=0;
    }
    不用保证 y 有序
    zjp
        4
    zjp  
       2021-04-09 00:35:38 +08:00
    不假设数组有序和不重复的情况
    int[] x = {1, 2, 3, 4, 5, 6, 7};
    int[] y = {2, 4, 7};
    Map<Integer, Long> count = Arrays.stream(y).boxed()
    .collect(Collectors.groupingBy(Function.identity(), Collectors.counting()));
    int[] z = Arrays.stream(x).boxed()
    .map(e -> count.containsKey(e) && count.put(e, count.get(e) - 1) > 0 ? e : 0)
    .mapToInt(Integer::intValue).toArray();
    System.out.println("z = " + Arrays.toString(z));
    zjp
        5
    zjp  
       2021-04-09 00:39:52 +08:00
    @zjp 对 IntStream 不熟悉,boxed 然后 mapToInt 是多余的
    LowBi
        6
    LowBi  
    OP
       2021-04-09 09:03:42 +08:00 via Android
    @javapythongo @LGA1150 @zjp 感谢大佬们提供代码思路
    no1xsyzy
        7
    no1xsyzy  
       2021-04-09 09:26:43 +08:00
    你这判断 a!=0 再 add 跟直接 z.add(a) 有什么区别(

    @LGA1150 你这有序是 O(m log n),m,n>4 的话还不如集合呢……
    有序的情况下最优应是仿归并排序的双指针移动
    youhuo
        8
    youhuo  
       2021-04-09 13:51:02 +08:00
    来学习 学习
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   2512 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 22ms · UTC 15:45 · PVG 23:45 · LAX 07:45 · JFK 10:45
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.