LintCode: Number of restaurants

Number of restaurants



Similar Problems:


Description
Give a List of data representing the coordinates[x,y] of each restaurant. Customer’s coordinates are at the origin[0,0].Find out the n restaurants closest to the customer ,return their coordinates in the original order.

  1. Coordinates in range [-1000,1000]
  2. n>0

Example

Given:

n = 2
List = [[0,0],[1,1],[2,2]]
Return:

[[0,0],[1,1]]

Github: code.dennyzhang.com

Credits To: lintcode.com

Leave me comments, if you have better ways to solve.


  • Solution:
## Blog link: https://code.dennyzhang.com/number-of-restaurants
## Basic Ideas: maxheap
## Complexity: Time O(max(r, n*log(n)), Space O(n)
##              r = len(restaurant)
import heapq

class Solution:
    """
    @param restaurant: 
    @param n: 
    @return: nothing
    """
    def nearestRestaurant(self, restaurant, n):
        if len(restaurant) < n: return []
        l = []
        heapq.heapify(l)
        for i, r in enumerate(restaurant):
            d = r[0]*r[0] + r[1]*r[1]
            heapq.heappush(l, (-d, i))
            if len(l) > n: heapq.heappop(l)

        l.sort(key=lambda x:x[1])
        res = []
        for (_, i) in l: res.append(restaurant[i])
        return res
linkedin
github
slack

Share It, If You Like It.

Leave a Reply

Your email address will not be published.