План курса / Все задачи / Алгоритмы и структуры данных
Симметрия по оси Y
средне
# решено
Дан массив точек points. Нужно вернуть true, если существует такая прямая, параллельная оси Y, которая симметрично отражает данные точки и false, если такой прямой нет.
ВАЖНО: точки могут повторяться, но число симметричных точек не обязательно должно совпадать (см. пример 1)
Ввод: points = [[4,2]]
Вывод: true
Объяснение: если точка лежит на прямой, то считаем ее симметричной самой себе.
Ограничения:
len(points) >= 1
public class Solution
{
public static bool IsSymmetric(List<List<int>> points)
{
int maxX = points[0][0];
int minX = points[0][0];
HashSet<(int, int)> pointsSet = new HashSet<(int, int)>();
foreach (var p in points)
{
maxX = Math.Max(maxX, p[0]);
minX = Math.Min(minX, p[0]);
pointsSet.Add((p[0], p[1]));
}
foreach (var (x, y) in pointsSet)
{
// Находим x-координату симметричной точки
int mirrorX = maxX + minX - x;
if (!pointsSet.Contains((mirrorX, y)))
{
return false;
}
}
return true;
}
}
#include <vector>
#include <unordered_set>
#include <algorithm>
#include <string>
using namespace std;
bool isSymmetric(const vector<vector<int>>& points) {
int maxX = points[0][0];
int minX = points[0][0];
unordered_set<string> pointsSet;
for (auto& p : points) {
maxX = max(maxX, p[0]);
minX = min(minX, p[0]);
pointsSet.insert(to_string(p[0]) + "," + to_string(p[1]));
}
for (auto& key : pointsSet) {
int comma = key.find(',');
int x = stoi(key.substr(0, comma));
int y = stoi(key.substr(comma + 1));
// находим x-координату симметричной точки
int mirrorX = maxX + minX - x;
if (pointsSet.find(to_string(mirrorX) + "," + to_string(y)) == pointsSet.end()) {
return false;
}
}
return true;
}
package main
func isSymmetric(points [][]int) bool {
maxX := points[0][0]
minX := points[0][0]
pointsSet := make(map[[2]int]struct{})
for _, p := range points {
if p[0] > maxX {
maxX = p[0]
}
if p[0] < minX {
minX = p[0]
}
pointsSet[[2]int{p[0], p[1]}] = struct{}{}
}
for point := range pointsSet {
// находим x-координату симметричной точки
mirrorX := maxX + minX - point[0]
if _, ok := pointsSet[[2]int{mirrorX, point[1]}]; !ok {
return false
}
}
return true
}
import java.util.*;
public class Solution {
record Point(int x, int y) {}
public boolean isSymmetric(List<List<Integer>> points) {
int maxX = points.get(0).get(0);
int minX = points.get(0).get(0);
Set<Point> pointsSet = new HashSet<>();
for (List<Integer> p : points) {
maxX = Math.max(maxX, p.get(0));
minX = Math.min(minX, p.get(0));
pointsSet.add(new Point(p.get(0), p.get(1)));
}
for (Point p : pointsSet) {
// находим x-координату симметричной точки
int mirrorX = maxX + minX - p.x();
if (!pointsSet.contains(new Point(mirrorX, p.y()))) {
return false;
}
}
return true;
}
}
from typing import *
def is_symmetric(points: List[List[int]]) -> bool:
max_x = points[0][0]
min_x = points[0][0]
points_set = set()
for x, y in points:
max_x = max(max_x, x)
min_x = min(min_x, x)
points_set.add((x, y))
for x, y in points_set:
# находим x-координату симметричной точки
mirror_x = max_x + min_x - x
if (mirror_x, y) not in points_set:
return False
return True
/**
* @param {number[][]} points
* @returns {boolean}
*/
export function isSymmetric(points) {
let maxX = points[0][0];
let minX = points[0][0];
const pointsSet = new Set();
for (const [x, y] of points) {
maxX = Math.max(maxX, x);
minX = Math.min(minX, x);
pointsSet.add(`${x},${y}`);
}
for (const key of pointsSet) {
const [x, y] = key.split(',').map(Number);
// находим x-координату симметричной точки
const mirrorX = maxX + minX - x;
if (!pointsSet.has(`${mirrorX},${y}`)) {
return false;
}
}
return true;
}
Оценка сложности
Время: O(n), где n - размер массива points
Память: O(n), где n - размер массива points
На собеседовании могут попросить доказать формулу maxX + minX - x. В большинстве случаем достаточно такого объяснения: симметричная точка должна быть на таком же расстоянии от оси симметрии, только в противоположную сторону, поэтому выполняется равенство: координата симметричной точки x' и исходной точки x расположены так, что x' − axis = axis − x, где axis — это координата вертикальной оси симметрии. Эта ось проходит ровно посередине между minX и maxX, то есть axis = (minX + maxX) / 2. Подставив это в формулу, получаем x' = 2·axis − x = (minX + maxX) − x.