2019-08-19.md

每日一题 - 593. 有效的正方形

信息卡片

• 时间：2019-06-08
• 题目链接：https://leetcode.com/problems/top-k-frequent-elements/description/
• tag：Hash Table Heap

题目描述

Given a non-empty array of integers, return the k most frequent elements.
 
Example 1:
 
Input: nums = [1,1,1,2,2,3], k = 2
Output: [1,2]

Example 2:


Input: nums = [1], k = 1
Output: [1] 
 
Note:  
 
You may assume k is always valid, 1 ≤ k ≤ number of unique elements.
Your algorithm's time complexity must be better than O(n log n), where n is
the array's size.

参考答案

模仿 @raof01 的思路写的JS代码，

基本思路就是： 证明四个角都是直角， 而证明直角的方式就是边长关系。

四个点一共有六个连接的线段，其中两个是对角线，另外四个是边。

对于直角来说，满足“a * a + b * b = c * c”, 由于是正方形，所以a = b， 因此c就等于 2 * a * a , 其中a为边长，c就是对角线的长度。

我们分别计算出距离的平方，如果有四个相同，另外两个相同。 且二者的关系可以满足直角，那么他就有四个直角，他就是一个正方形

/*
 * @lc app=leetcode id=593 lang=javascript
 *
 * [593] Valid Square
 */
function square(p1, p2) {
    const deltaX = p1[0] - p2[0];
    const deltaY = p1[1] - p2[1];

    return deltaX * deltaX + deltaY * deltaY;
}
/**
 * @param {number[]} p1
 * @param {number[]} p2
 * @param {number[]} p3
 * @param {number[]} p4
 * @return {boolean}
 */
var validSquare = function (p1, p2, p3, p4) {
  // 证明四个角都是直角
  // 证明直角的方式就是边长关系
  const squares = [
    square(p1, p2),
    square(p1, p3),
    square(p1, p4),
    square(p2, p3),
    square(p2, p4),
    square(p3, p4)
  ];
  let cnt1 = 0;
  let cnt2 = 0;
  let sum = 0;

  for(let i = 0; i < squares.length; i++) {
    sum += squares[i];
  }

  for(let i = 0; i < squares.length; i++) {
      if (sum === 8 * squares[i]) {
          cnt1++;
      } else if(sum === 4 * squares[i]) {
          cnt2++;
      }
  }

  return cnt1 === 4 && cnt2 ===2;
  
}

其他优秀解答

暂无