4

LintCode 460.在排序数组中找最接近的K个数

 2 years ago
source link: https://www.purewhite.io/2018/07/11/lintcode-find-k-closest-elements/
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
neoserver,ios ssh client

LintCode 460. 在排序数组中找最接近的 K 个数

发表于 2018-07-11 更新于 2021-12-02 分类于 算法 阅读次数： Disqus： 本文字数： 1.4k 阅读时长 ≈ 2 分钟

给一个目标数 target, 一个非负整数 k, 一个按照升序排列的数组 A。在 A 中找与 target 最接近的 k 个整数。返回这 k 个数并按照与 target 的接近程度从小到大排序，如果接近程度相当，那么小的数排在前面。

The value k is a non-negative integer and will always be smaller than the length of the sorted array.

Length of the given array is positive and will not exceed 10^4

Absolute value of elements in the array and x will not exceed 10^4

如果 A = [1, 2, 3], target = 2 and k = 3, 那么返回 [2, 1, 3].

如果 A = [1, 4, 6, 8], target = 3 and k = 3, 那么返回 [4, 1, 6].

这道题的一般解法都很容易想出来，暴力出奇迹嘛，这里我们只说最优解，也就是 O (logn + k) 的时间复杂度 的解法。

这道题的解题关键是数组 A 是有序的，只要有序就可以考虑用二分。

我们通过对 A 进行二分，找到最接近 target 的数，找到之后用双指针的思想，依次从找到的那个数向两边扩散，直到满足 k 个数为止。

思路较为简单，编码过程注意一些边界条件的判断即可。

class Solution:
    """
    @param A: an integer array
    @param target: An integer
    @param k: An integer
    @return: an integer array
    """
    def kClosestNumbers(self, A, target, k):
        if k == 0:
            return []
        if not A:
            return []
        lp = None
        rp = None
        start = 0
        end = len(A) - 1
        while start + 1 < end:
            mid = int(start + (end - start) / 2)
            if A[mid] == target:
                start = mid
                end = mid + 1
                break
            elif A[mid] < target:
                start = mid
            else:
                end = mid
        if abs(A[start] - target) <= abs(A[start] - target):
            lp = start
            rp = end
        else:
            lp = end
            rp = end + 1
        cnt = 0
        ans = list()
        while cnt < k:
            cnt += 1
            if lp < 0 and rp >= len(A):
                return []
            elif lp < 0:
                ans.append(A[rp])
                rp += 1
            elif rp >= len(A):
                ans.append(A[lp])
                lp -= 1
            elif abs(A[lp] - target) <= abs(A[rp] - target):
                ans.append(A[lp])
                lp -= 1
            else:
                ans.append(A[rp])
                rp += 1
        return ans

report

Recommend

About Joyk


Aggregate valuable and interesting links.
Joyk means Joy of geeK