Leetcode|Find K Closest Elements

01

题目

Given a sorted array, two integers k and x, find the k closest elements to x in the array. The result should also be sorted in ascending order. If there is a tie, the smaller elements are always preferred.

Input: [1,2,3,4,5], k=4, x=3 Output: [1,2,3,4]

Input: [1,2,3,4,5], k=4, x=-1Output: [1,2,3,4]

Note: The value k is positive and will always be smaller than the length of the sorted array. Length of the given array is positive and will not exceed 104 Absolute value of elements in the array and x will not exceed 104

题目的意思是求出与x最相近的k个元素

02

分析

考虑两种特殊情况:

  1. x 小于等于 arr[0]
  2. x 大于等于 arr[-1]

然后,考虑一般情况,这时与x的距离,分布情况为:与x的距离先降为0,然后再逐渐增大,所以里面又有两种可能:

  1. 距离等于0的元素个数大于或等于k
  2. 距离等于0的元素个数小于k,这种情况求解,稍微复杂,需要二分动态查找。

以上分析的时间复杂度为O(n),空间复杂度为O(1)。

03

python代码


"""
arr: array wanted to search
k : k numbers nearest to x
x: goal center point
assert:
  1. arr is sorted
  2. ele in arr is integer
"""
def findKNearestToX(arr=[1,3,5],k=2,x=0):
    # x less or equal than arr[0]
    if x <= arr[0]:
        return arr[:k]
    # x bigger or equal than arr[-1]
    if x >= arr[-1]:
        return arr[-k:]
    # ordinary cases: at least one zero,
    # distance distribution: decline-->0-->rise
    hi=0
    zerolen=0
    for i,item in enumerate(arr):
        item = abs(item-x)
        if item==0:
            hi=i
            zerolen+=1
            if zerolen == k:
                return arr[hi-zerolen+1:hi+1]
    # here shows: number of zero chunk is less than k
    # then it needs to dynamic binary search
    lo = hi - zerolen+1
    curlen = zerolen
    while curlen < k:
        if lo > 0 and abs(arr[lo-1]-x) <= abs(arr[hi+1]-x):
            lo-=1
        elif hi < len(arr):
            hi+=1
        curlen+=1
    return arr[lo:hi+1]

#单元test
#1
kNearest = findKNearestToX(arr=[1,3,5],k=2,x=0)
#2
kNearest = findKNearestToX(arr=[1,3,5],k=2,x=5)
#3
#3-1
kNearest = findKNearestToX(arr=[1,3,3,3,5],k=2,x=3)
#3-2
kNearest = findKNearestToX(arr=[1,3,4,5],k=3,x=3)
#3-3
kNearest = findKNearestToX(arr=[-1,3,4,4],k=3,x=3)
print(kNearest)

原文发布于微信公众号 - 算法channel(alg-channel)

原文发表时间:2018-01-11

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏前端吧啦吧啦

数据结构(二)之算法基础

3827
来自专栏程序生活

连续子数组的最大和

题目1 连续子数组的最大和 描述: 输入一个整型数组,数组里有正数也有负数。数组中一个或连续的多个整数组成一个子数组。求所有子数组的和的最大值。要求时间复杂度...

2965
来自专栏个人随笔

房上的猫:二维数组

二维数组是数组的数组。 二维数组基础   基本的定义方式有两种形式,如:   int [][] i = new int[2][3];(推荐)   int i...

2948
来自专栏kalifaの日々

线段树 BIT 求冒泡排序的交换次数

线段树特别适合与区间相关的运算,比如MRQ(minimum range query)求一段区间内的最小值。 BIT可以看作是压缩了的线段树,由于(某类)线段树...

4148
来自专栏Leetcode名企之路

【Leetcode】81. 搜索旋转排序数组 II

( 例如,数组 [0,0,1,2,2,5,6] 可能变为 [2,5,6,0,0,1,2] )。

1572
来自专栏计算机视觉与深度学习基础

全排列生成算法:next_permutation

概念 全排列的生成算法有很多种,有递归遍例,也有循环移位法等等。C++/STL中定义的next_permutation和prev_permutation函数则...

2136
来自专栏前端吧啦吧啦

数据结构(二)之算法基础

1264
来自专栏我是业余自学C/C++的

矩阵

1395
来自专栏chenjx85的技术专栏

leetcode-884-两句话中的不常见单词

给定两个句子 A 和 B 。 (句子是一串由空格分隔的单词。每个单词仅由小写字母组成。)

1393
来自专栏Python小屋

Python高级数组处理模块numpy用法精要

numpy是Python的高级数组处理扩展库,提供了Python中没有的数组对象,支持N维数组运算、处理大型矩阵、成熟的广播函数库、矢量运算、线性代数、傅里叶变...

4047

扫码关注云+社区