列表

详情


NC404. 最接近的K个元素

描述

给定一个长度为 n 的升序数组 nums 和两个整数 k 和 x ,从数组中找到最接近 x (两数之差最小)的 k 个数并升序得输出他们。

整数 a 比整数 b 更接近 x 需要满足
|a-x| < |b-x| ,
|a-x| = |b-x| 时 a < b

数据范围:

示例1

输入:

[1,2,3,4,5],4,4

输出:

[2,3,4,5]

示例2

输入:

[1,2,3,4,5],4,3

输出:

[1,2,3,4]

示例3

输入:

[1,2,3,4],4,0

输出:

[1,2,3,4]

原站题解

上次编辑到这里,代码来自缓存 点击恢复默认模板

C 解法, 执行用时: 23ms, 内存消耗: 3080KB, 提交时间: 2022-06-28

/**
 * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
 *
 * 
 * @param nums int整型一维数组 
 * @param numsLen int nums数组长度
 * @param k int整型 
 * @param x int整型 
 * @return int整型一维数组
 * @return int* returnSize 返回数组行数
 *
 * C语言声明定义全局变量请加上static,防止重复定义
 */
int* closestElement(int* nums, int numsLen, int k, int x, int* returnSize ) {
    int closestIndex = -1, lastGap = 200001, gap, minGap = 200001;
    for (int i = 0; i < numsLen; i++) {
        gap = abs(nums[i] - x);
        if (gap < minGap) {
            minGap = gap;
            closestIndex = i;
        }
        if (gap > lastGap) {
            break;
        }
        lastGap = gap;
    }
    
    int left, right, leftGap, rightGap, count = 1;
    if (closestIndex == 0) {
        left = 0;
        right = k - 1;
    } else if (closestIndex == numsLen - 1) {
        left = numsLen - k;
        right = numsLen - 1;
    } else if (k == 1) {
        left = closestIndex;
        right = closestIndex;
    } else {
        left = closestIndex - 1;
        right = closestIndex + 1;
        
        while(left >= 0 && right <= numsLen - 1 && count < k) {
            leftGap = abs(nums[left] - x);
            rightGap = abs(nums[right] - x);
            if (leftGap <= rightGap) {
                if (left == 0) {
                    right = k - 1;
                    break;
                }
                left--;
                count++;
                if (count == k) {
                    left++;
                    right--;
                }
            } else {
                if (right == numsLen - 1) {
                    left = numsLen - k;
                    break;
                }
                right++;
                count++;
                if (count == k) {
                    left++;
                    right--;
                }
            }
        }
    }
    
    *returnSize = k;
    int *result = (int *)malloc(sizeof(int) * k);
    for (int i = 0; i < k; i++) {
        result[i] = nums[left+i];
    }
    return result;
}




C++ 解法, 执行用时: 24ms, 内存消耗: 3140KB, 提交时间: 2022-06-09

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
     *
     * 
     * @param nums int整型vector 
     * @param k int整型 
     * @param x int整型 
     * @return int整型vector
     */
    vector<int> closestElement(vector<int>& nums, int k, int x) {
        // write code here
        vector<int> res;
        int n=nums.size();
        int l=0,r=n-k;
        while(l<r){
            int m=l+(r-l)/2;
            if(abs(nums[m]-x)>abs(nums[m+k]-x)){
                l=m+1;
            }
            else r=m;
        }
        while(k--){
            res.push_back(nums[l]);
            l++;
        }
        return res;
    }
};

C++ 解法, 执行用时: 26ms, 内存消耗: 3140KB, 提交时间: 2022-07-24

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
     *
     * 
     * @param nums int整型vector 
     * @param k int整型 
     * @param x int整型 
     * @return int整型vector
     */
    //[1, 2, 3, 4, 5], 4, 3
    vector<int> closestElement(vector<int>& nums, int k, int x) {
        // write code here
        vector<int> res;
        int n=nums.size();
        int l=0,r=n-k;
        while(l<r){
            int mid=(r+l)/2;
            if(abs(nums[mid]-x)>abs(nums[mid+k] -x)) l=mid+1;
            else r=mid;
        }
        while(k--){
            res.emplace_back(nums[l++]);
        }
        return res;
    }
};

C++ 解法, 执行用时: 26ms, 内存消耗: 3156KB, 提交时间: 2022-08-06

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
     *
     * 
     * @param nums int整型vector 
     * @param k int整型 
     * @param x int整型 
     * @return int整型vector
     */
    vector<int> closestElement(vector<int>& nums, int k, int x) {
        // write code here
        vector<int> res;
        int n=nums.size();
        int l=0,r=n-k;
        while(l<r)
        {
            int m=l+(r-l)/2;
            if(abs(nums[m]-x)>abs(nums[m+k]-x))
            {
                l=m+1;
            }
            else
                r=m;
        }
        while(k--)
        {
            res.push_back(nums[l]);
            l++;
        }
        return res;
        
    }
};

C++ 解法, 执行用时: 28ms, 内存消耗: 3128KB, 提交时间: 2022-07-30

class Solution {
  public:
    vector<int> closestElement(vector<int>& nums, int k, int x) {
        vector<int> v;
        int h = nums.size();
        int L = 0, R = h - k;
        while (L < R) {
            int m = L + (R - L) / 2;
            if (abs(nums[m] - x) > abs(nums[m + k] - x)) {
                L = m + 1;
            } else R = m;
        }
        while (k--) {
            v.push_back(nums[L]);
            L++;
        }
        return v;
    }
};

上一题