M时间的Big-oh中的坐标之间的距离 [英] Distance between coordinates in Big-oh of M time

问题描述

我有一个坐标数组，即每个索引都包含(x，y)坐标.我想弄清楚是否有任何坐标在单行或单列中.挑战是在单个循环中进行，其中M是数组的长度.我一直在努力，但如果不使用两个循环，似乎无法做到这一点.只是需要有关算法的帮助.

I have an array of coordinates, i.e each index contains (x,y) coordinates. I want to figure out that if any of the coordinates are in single row or column. The challenge is to do in a single loop where M is the length of the array. I have been trying hard but cant seem to do it without using two loops. Just need help with the algorithm.

基本上问题是我在N x N板上有M个棋子.每块都可以任意水平和垂直移动任意数量.只想弄清楚是否有任何一块可以攻击其他任何一块.

Basically the problem is that I have M pieces on an N by N board. Each piece can move any vertically and horizontally by any number. Just want to figure out that if any piece can attack any other piece.

推荐答案

这是元素唯一性/唯一性问题在通常情况下(即排序)具有复杂度O(MLogm).

This is element distinctness/uniqueness problem that has complexity O(MLogm) in common case (i.e. sorting).

如果没有内存限制，则可以将哈希表用于Y和X坐标，在这种情况下，单次遍历数组可以解决问题

If there are no memory limitations, you can use hash tables for Y and X coordinates, in this case single run through array solves the problem

对于有限的电路板，对于水平和垂直方向使用布尔数组长度N更简单.时间复杂度O(M)，内存消耗O(N)

For limited board it is simpler to use boolean array length N for horizontals and verticals. Time complexity O(M), memory consumption O(N)

for every rook:
    if Horiz[rook.Y] then
        two rooks share horizontal
    if Vert[rook.X] then
        two rooks share the same vertical
    Horiz[rook.Y] = True
    Vert[rook.X] = True

这篇关于M时间的Big-oh中的坐标之间的距离的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！