Valid square 和 follow up的时间复杂度

LC 593, 时间复杂度是O（1），因为只有四个点。

F

您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Popular Interview Questions from Top Companies

(n^2)呢

1. class Solution {
   
2.     // Calculate each pair's distance
   
3.     // If distance ==0, return false
   
4.     // else put distance into a set
   
5.     // When finished, if set just contains 2 value
   
6.     // return true; else return false
   
7.    public boolean validSquare(int[] p1, int[] p2, int[] p3, int[] p4) {
   
8.         // Tell if the point is valid
   
9.         // Put four points into a list
   
10.         List<int[]> list = new LinkedList<>();
    
11.         list.add(p1);
    
12.         list.add(p2);
    
13.         list.add(p3);
    
14.         list.add(p4);
    
15.         
    
16.         for(int[] p : list){
    
17.             if(p == null || p.length != 2)
    
18.                 return false;
    
19.         }
    
20.         Set<Integer> set = new HashSet<>();
    
21.         for(int i = 0; i < 3; i ++){
    
22.             for(int j = i + 1; j < 4; j ++){
    
23.                 int[] px = list.get(i);
    
24.                 int[] py = list.get(j);
    
25.                 int distance = calDistance(px, py);
    
26.                 if(distance == 0)
    
27.                     return false;
    
28.                 set.add(distance);
    
29.             }
    
30.         }
    
31.         return set.size() == 2;
    
32.     }
    
33.     private int calDistance(int[] p1, int[] p2){
    
34.         int x1 = p1[0], y1 = p1[1];
    
35.         int x2 = p2[0], y2 = p2[1];
    
36.         return (x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2);   
    
37.     }
    
38.     // The follow up question is, given a series of point, tell number of squares.
    
39.     // First of all, tell if the list contains at least 4 points
    
40.    public int validSquareII(List<int[]> list){
    
41.        if(list == null || list.size() < 4)
    
42.            return 0;
    
43.        int length = list.size();
    
44.        int result = 0;
    
45.        for(int i = 0; i < length - 3; i ++){
    
46.            for(int j = i + 1; j < length - 2; j ++){
    
47.                for(int k = j + 1; k < length -1; k ++){
    
48.                    for(int l = k + 1; l < length; l ++){
    
49.                        int[] p1 = list.get(i);
    
50.                        int[] p2 = list.get(j);
    
51.                        int[] p3 = list.get(k);
    
52.                        int[] p4 = list.get(l);
    
53.                        if (validSquare(p1,p2,p3,p4)){
    
54.                            result ++;
    
55.                        }
    
56.                    }
    
57.                }
    
58.            }
    
59.        }
    
60.        return result;   
    
61.    }
    
62. 
    
63. }

复制代码

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Popular Interview Questions from Top Companies