算法-最快速度求两个数组之交集算法

柔光的暖阳◎ 2022-12-06 12:39 142阅读 0赞

# 1. DSU（并查集） #

1.  条件:需要查询小范围的数据集合，不包含特殊数字。同时数字>=1。

思路：使用数组hash。index代表集合中的数。value为代表集合。

class DSU { 
            int[] parent;
    		//可初始化大小
            public DSU() { 
                parent = new int[10001];
                for (int i = 0; i <= 10000; ++i)
                    parent[i] = i;
            }
    
            /** * 找到x的父类 * * @param x * @return */
            public int find(int x) { 
    
                if (parent[x] != x) parent[x] = find(parent[x]);
                return parent[x];
            }
    
            public void union(int x, int y) { 
                parent[find(x)] = find(y);
            }
        }
          public void findUnion(int[] a, int[] b) { 
            DSU dsu = new DSU();
            for (int i = 0; i < a.length; i++) { 
                dsu.union(a[i], 0);
            }
            for (int i = 0; i < b.length; i++) { 
                if (dsu.find(b[i]) == 0) { 
                    System.out.println(b[i]);
                }
            }
        }

时间复杂度O（m+n）空间复杂大为a中最大数字。所以说存在限制条件。只能处理最多（1->正无穷的数字），我们需要0作为并查集的父。

# 2. 排序指针移动 #

//排好序后比较移动指针
    public int[] findUnion(int[] nums1, int[] nums2) { 
    		Arrays.sort(nums1);
    		Arrays.sort(nums2);
    		int len1=nums1.length;
    		int len2=nums2.length;
    		ArrayList<Integer> al=new ArrayList<Integer>();
    		for(int i=0,j=0;i<len1 && j<len2;) { 
    			if(nums1[i] == nums2[j]) { 
    				al.add(nums1[i]);
    				i++;
    				j++;
    			}
    			else if(nums1[i] > nums2[j]) { 
    				j++;
    			}
    			else { 
    				i++;
    			}	
    		}
     
    		int[] in = new int[al.size()];
    		int e=0;
    		for(int i:al)
    			in[e++] = i;
    		return in;
    	}

# 3. Hash算法 #

可用HashSet，或者HashMap进行完成。  
Hash的快速查找通过key的hashcode进行完成，可快速定位到桶，O（1）。  
可做之前放入个数比较小的数组，然后遍历另外一个数组来查找，是否在Hash的数据结构中。完成交集算法。