首页 > 代码库 > Coursera Algorithms week2 基础排序 Interview Questions: 1 Intersection of two sets
Coursera Algorithms week2 基础排序 Interview Questions: 1 Intersection of two sets
题目原文:
Given two arrays a[] and b[], each containing n distinct 2D points in the plane, design a subquadratic algorithm to count the number of points that are contained both in array a[] and array b[].
题目的目标就是计算重复point的个数,很简单,代码如下
1 import java.awt.Point; 2 import java.util.Arrays; 3 import java.util.HashSet; 4 import java.util.Set; 5 6 import edu.princeton.cs.algs4.StdRandom; 7 8 public class PlanePoints { 9 private Set<Point> s = new HashSet<Point>(); 10 private int samePointsNum; 11 PlanePoints(int n,Point[] inputa, Point[] inputb){ 12 for(int i=0;i<n;i++){ 13 s.add(inputa[i]); 14 s.add(inputb[i]); 15 } 16 samePointsNum = 2*n - s.size(); 17 } 18 19 public int samePointsNum(){ 20 return samePointsNum; 21 } 22 23 public static void main(String[] args){ 24 int n = 10; 25 Point[] a = new Point[n]; 26 Point[] b = new Point[n]; 27 System.out.println(a.length); 28 for(int i=0;i<n;i++){ 29 a[i] = new Point(); 30 a[i].setLocation(StdRandom.uniform(n), StdRandom.uniform(n)); 31 b[i] = new Point(); 32 b[i].setLocation(StdRandom.uniform(n), StdRandom.uniform(n)); 33 } 34 System.out.println(Arrays.toString(a)); 35 System.out.println(Arrays.toString(b)); 36 PlanePoints pp = new PlanePoints(n,a,b); 37 System.out.println(pp.samePointsNum); 38 } 39 }
Coursera Algorithms week2 基础排序 Interview Questions: 1 Intersection of two sets
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。