План курса / Все задачи / Алгоритмы и структуры данных
Строгая симметрия по оси Y
средне
# решено
Дан массив точек points. Нужно вернуть true, если существует такая прямая, параллельная оси Y, которая симметрично отражает все данные точки и false, если такой прямой нет.
ВАЖНО: При этом каждая точка должна иметь симметричную ей точку в массиве с таким же числом вхождений. Если же точка имеет координату X равную оси симметрии, то она симметрична сама себе в любом случае.
public class Solution
{
public static bool IsSymmetric(List<List<int>> points)
{
int maxX = points[0][0];
int minX = points[0][0];
Dictionary<(int, int), int> pointsMap = new Dictionary<(int, int), int>();
foreach (var p in points)
{
maxX = Math.Max(maxX, p[0]);
minX = Math.Min(minX, p[0]);
var key = (p[0], p[1]);
if (!pointsMap.ContainsKey(key))
pointsMap[key] = 0;
pointsMap[key]++;
}
foreach (var entry in pointsMap)
{
// Находим x-координату симметричной точки
int mirrorX = maxX + minX - entry.Key.Item1;
var mirrorKey = (mirrorX, entry.Key.Item2);
// Сравниваем частоты текущей точки и симметричной
if (!pointsMap.ContainsKey(mirrorKey) || pointsMap[mirrorKey] != entry.Value)
{
return false;
}
}
return true;
}
}
#include <vector>
#include <unordered_map>
#include <algorithm>
#include <string>
using namespace std;
bool isSymmetric(vector<vector<int>>& points) {
int maxX = points[0][0];
int minX = points[0][0];
unordered_map<string, int> pointsMap;
for (auto& p : points) {
maxX = max(maxX, p[0]);
minX = min(minX, p[0]);
string key = to_string(p[0]) + "," + to_string(p[1]);
pointsMap[key]++;
}
for (auto& [key, freq] : pointsMap) {
// извлекаем координаты из ключа
int comma = key.find(',');
int x = stoi(key.substr(0, comma));
int y = stoi(key.substr(comma + 1));
// находим x-координату симметричной точки
int mirrorX = maxX + minX - x;
string mirrorKey = to_string(mirrorX) + "," + to_string(y);
// сравниваем частоты текущей точки и симметричной
auto it = pointsMap.find(mirrorKey);
if (it == pointsMap.end() || it->second != freq) {
return false;
}
}
return true;
}
package main
func isSymmetric(points [][]int) bool {
maxX := points[0][0]
minX := points[0][0]
pointsMap := make(map[[2]int]int)
for _, p := range points {
if p[0] > maxX {
maxX = p[0]
}
if p[0] < minX {
minX = p[0]
}
pointsMap[[2]int{p[0], p[1]}]++
}
for point, freq := range pointsMap {
// находим x-координату симметричной точки
mirrorX := maxX + minX - point[0]
mirror := [2]int{mirrorX, point[1]}
// сравниваем частоты текущей точки и симметричной
if pointsMap[mirror] != freq {
return false
}
}
return true
}
import java.util.*;
public class Solution {
public boolean isSymmetric(List<List<Integer>> points) {
int maxX = points.get(0).get(0);
int minX = points.get(0).get(0);
Map<String, Integer> pointsMap = new HashMap<>();
for (List<Integer> p : points) {
maxX = Math.max(maxX, p.get(0));
minX = Math.min(minX, p.get(0));
String key = p.get(0) + "," + p.get(1);
pointsMap.put(key, pointsMap.getOrDefault(key, 0) + 1);
}
for (Map.Entry<String, Integer> entry : pointsMap.entrySet()) {
String[] parts = entry.getKey().split(",");
int x = Integer.parseInt(parts[0]);
int y = Integer.parseInt(parts[1]);
// находим x-координату симметричной точки
int mirrorX = maxX + minX - x;
String mirrorKey = mirrorX + "," + y;
// сравниваем частоты текущей точки и симметричной
if (!pointsMap.containsKey(mirrorKey) || !pointsMap.get(mirrorKey).equals(entry.getValue())) {
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_map = {}
for x, y in points:
max_x = max(max_x, x)
min_x = min(min_x, x)
points_map[(x, y)] = points_map.get((x, y), 0) + 1
for (x, y), freq in points_map.items():
# находим x-координату симметричной точки
mirror_x = max_x + min_x - x
# сравниваем частоты текущей точки и симметричной
if points_map.get((mirror_x, y)) != freq:
return False
return True
/**
* @param {number[][]} points
* @returns {boolean}
*/
export function isSymmetric(points) {
let maxX = points[0][0];
let minX = points[0][0];
const pointsMap = {};
for (const [x, y] of points) {
maxX = Math.max(maxX, x);
minX = Math.min(minX, x);
const key = `${x},${y}`;
pointsMap[key] = (pointsMap[key] || 0) + 1;
}
for (const [key, freq] of Object.entries(pointsMap)) {
const [x, y] = key.split(',').map(Number);
// находим x-координату симметричной точки
const mirrorX = maxX + minX - x;
const mirrorKey = `${mirrorX},${y}`;
// сравниваем частоты текущей точки и симметричной
if (pointsMap[mirrorKey] !== freq) {
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.