Problem description

Given array a[N], Can be determined C(N,2) A point is right , That's for sure C(N,2) Distance , Find the second of these distances k A small distance (k<C(N,2)).

Ideas

See the k Small 、 The first k It's a big problem , First think of dichotomy .

Turn the evaluation problem into : How many elements are less than this value .

The interval problem of this problem needs careful consideration , Consider the need for an equal sign in all places where a less than sign appears .

Code

class Solution:
def smallestDistancePair(self, nums, k):
"""
:type nums: List[int]
:type k: int
:rtype: int
"""
nums = sorted(nums)
l = 0
r = nums[-1] - nums[0] def find(m):
s = 0
j = 0
for i in range(len(nums)):
while j < len(nums) and nums[j] - nums[i] <= m:
j += 1
s += j - i - 1
return s while l< r:
m = (l + r) // 2
s = find(m)
if s >= k:
r = m
else:
l = m+1
return l

leetcode719: The second on the line k More related articles in the near point

  1. lintcode Medium question :Max Points on a Line How many points are in a straight line at most

    subject How many points are in a straight line at most Give... On a two-dimensional plane n A little bit , Find out how many points are in the same line at most . Examples give 4 A little bit :(1, 2), (3, 6), (0, 0), (1, 3). A point on a straight line has at most 3 individual . ...

  2. BZOJ3403: [Usaco2009 Open]Cow Line Cattle in a straight line

    3403: [Usaco2009 Open]Cow Line Cattle in a straight line Time Limit: 3 Sec  Memory Limit: 128 MBSubmit: 48  Solved: 41[S ...

  3. BZOJ 3403: [Usaco2009 Open]Cow Line Cattle in a straight line ( deque )

    Direct use STL Of course deque Just fine ... ---------------------------------------------------------------------- #include& ...

  4. 3403: [Usaco2009 Open]Cow Line Cattle in a straight line

    3403: [Usaco2009 Open]Cow Line Cattle in a straight line Time Limit: 3 Sec  Memory Limit: 128 MBSubmit: 71  Solved: 62[S ...

  5. opencv utilize hough After fitting the straight line with probability transformation , utilize DDA The algorithm gets the coordinates of the pixels on the line

    After the image is fitted with a straight line by Hough transform , How to get the coordinates of the pixels on the line ? This is the problem I met in my study of image processing today , The probability Hough transform used in Hough transform , So the line information obtained by fitting is actually the coordinates of the two endpoints of the line , A more direct way of thinking is ...

  6. [Swift]LeetCode149. The most points on the line | Max Points on a Line

    Given n points on a 2D plane, find the maximum number of points that lie on the same straight line. ...

  7. lintcode-186- How many points are in a straight line at most

    186- How many points are in a straight line at most Give... On a two-dimensional plane n A little bit , Find out how many points are in the same line at most . Examples give 4 A little bit :(1, 2), (3, 6), (0, 0), (1, 3). A point on a straight line has at most 3 individual . ...

  8. 【BZOJ】3403: [Usaco2009 Open]Cow Line Cattle in a straight line ( simulation )

    http://www.lydsy.com/JudgeOnline/problem.php?id=3404 Bare two terminal queues .. #include <cstdio> #include <c ...

  9. B3403 [Usaco2009 Open]Cow Line Cattle in a straight line deque

    deque It's a real show ,queue and stack... It's no use . The operation is almost , It's just adding one in front of it front||back_ That's it . stem : Title Description Title Description      John's N A cow ( Make up for 1 To N Number ) Waiting in line ...

Random recommendation

  1. OVS All kinds of network devices in - Every day 5 Minutes to play OpenStack(128)

    In the last section we started Open vSwitch, This section will look at the current state of the network and introduce Open vSwitch All kinds of network equipment involved Initial network state Check out the current state of the network . The control node ifconfig Display control section ...

  2. How do you use it? Delphi Gets the current time , Accurate to milliseconds

    Let's first introduce a method that may be commonly used , Get the current time var datetime: string; begin datetime:= FormatDateTime('yyyy-mm-dd hh:mm:ss', N ...

  3. POMDP

    In this paper, from :http://www.pomdp.org/ One .Background on POMDPs We assume that the reader is familiar with the val ...

  4. LR Common functions

    1, Variable to parameter lr_save_string("aaa","param"): The string "aaa" Or a string variable , Into a LR Parameters of {param ...

  5. cmdb models database structure

    from __future__ import unicode_literals from django.contrib.auth.models import User from django.db i ...

  6. ubuntu 12.04 clang 3.4 install

    author :jostree  Reprint please indicate the source  http://www.cnblogs.com/jostree/p/4137402.html 1. add to clang Source deb http://llvm.org/apt/ ...

  7. java Take two decimal places Do not round off , How do you do it?

    java Take two decimal places Do not round off , How do you do it? Normal version : // Normal version : import java.text.DecimalFormat; import java.math.RoundingMode; De ...

  8. be based on jQuery Image waterfall flow implementation

    Their thinking : The first 1 Step   To analyze problems : My way of dealing with it is in columns . Each time the scroll bar rolls to the bottom , Put the new content that needs to be added in the column with the lowest height . As shown in the figure below Display after loading If you keep rolling down . The new picture will be in 1 The bottom shows , And so on . ...

  9. ajax Submit Form 、ajax File upload

    ajax Submit Form .ajax File upload , Friends in need can refer to . Mode one : utilize from Form targer attribute + Hidden iframe To achieve a similar effect , Support to submit complex forms containing files and common data Mode two : Use ...

  10. PyMongo Translation of official documents ——VNPY

    PyMongo yes MongoDB Database python modular VNPY Default database , There is no SQL Database of type , instead No-Sql Type of MongoDB database , For wanting to understand VNPY Children's shoes with internal structure , More or less ...