经典算法实例：有效的回旋镖

我们先来看题目描述：

给定一个数组 points ，其中 points [ i ] = [ xi, yi ] 表示 X-Y 平面上的一个点，如果这些点构成一个回旋镖则返回 true 。

回旋镖定义为一组三个点，这些点各不相同且不在一条直线上 。

示例 1 :

输入：points = [[1,1],[2,3],[3,2]] 输出：true

示例 2 :

输入：points = [[1,1],[2,2],[3,3]] 输出：false

提示：

• points.length == 3
• points[i].length == 2
• 0 <= xi, yi <= 100

解决方案

方法：向量叉乘

思路和算法计算从 points [0] 开始，分别指向 points [1] 和 points [2] 的向量 V1 和 V2 。「三点各不相同且不在一条直线上」等价于「这两个向量的叉乘结果不为零」：v1 + v2 ≠ 0

代码

Python3

class Solution: def isBoomerang(self, points: List[List[int]]) -> bool: v1 = (points[1][0] - points[0][0], points[1][1] - points[0][1]) v2 = (points[2][0] - points[0][0], points[2][1] - points[0][1]) return v1[0] * v2[1] - v1[1] * v2[0] != 0

C++

class Solution { public: bool isBoomerang(vector<vector<int>>& points) { vector<int> v1 = {points[1][0] - points[0][0], points[1][1] - points[0][1]}; vector<int> v2 = {points[2][0] - points[0][0], points[2][1] - points[0][1]}; return v1[0] * v2[1] - v1[1] * v2[0] != 0; } };

Java

class Solution { public boolean isBoomerang(int[][] points) { int[] v1 = {points[1][0] - points[0][0], points[1][1] - points[0][1]}; int[] v2 = {points[2][0] - points[0][0], points[2][1] - points[0][1]}; return v1[0] * v2[1] - v1[1] * v2[0] != 0; } }

复杂度分析

时间复杂度： O(1) 。

空间复杂度： O(1) 。