首页 > 其他分享 >LeetCode/找k个最接近元素

LeetCode/找k个最接近元素

时间:2022-08-25 00:55:28浏览次数:51  
标签:begin right int 元素 arr vector 接近 LeetCode left

给定排序好的数组 arr ,两个整数 k 和 x ,从数组中找到最靠近 x(两数之差最小)的 k 个数。返回的结果必须要是按升序排好的

1. 通用调库解法

class Solution {
public:
    vector<int> findClosestElements(vector<int>& arr, int k, int x) {
        sort(arr.begin(), arr.end(), [x](int a, int b) -> bool {
            return abs(a - x) < abs(b - x) || abs(a - x) == abs(b - x) && a < b;});
        //注意vector的指针实际上是左闭右开
        sort(arr.begin(), arr.begin() + k);
        return vector<int>(arr.begin(), arr.begin() + k);
    }
};

2. 二分法+双指针

class Solution {
public:
    vector<int> findClosestElements(vector<int>& arr, int k, int x) {
        int right = lower_bound(arr.begin(), arr.end(), x) - arr.begin();//第一个大于x的值下标
        int left = right - 1;//小于等于x的值下标
        while (k--) {//循环找k次,此时left、right皆为开区间
            if (left < 0) right++;//左指针溢出
            else if (right >= arr.size()) left--;//右指针溢出
            else if (x - arr[left] <= arr[right] - x) left--;//左侧值相等或更小移动左指针
            else right++;//否则移动右指针
        }
        //实际上输出的是[left+1,right-1]区间
        return vector<int>(arr.begin() + left + 1, arr.begin() + right);
    }
};

标签:begin,right,int,元素,arr,vector,接近,LeetCode,left
From: https://www.cnblogs.com/929code/p/16622867.html

相关文章

  • LeetCode 1. 两数之和
    题目题目链接:https://leetcode-cn.com/problems/two-sum/给定一个整数数组nums和一个目标值target,请你在该数组中找出和为目标值的那两个整数,并返回他们在数组里的下标。......
  • leetcode 594. Longest Harmonious Subsequence 最长和谐子序列(简单).md
    一、题目大意https://leetcode.cn/problems/longest-harmonious-subsequence和谐数组是指一个数组里元素的最大值和最小值之间的差别正好是1。现在,给你一个整数数组......
  • LeetCode 重排链表算法题解 All In One
    LeetCode重排链表算法题解AllInOnejs/ts实现重排链表重排链表原理图解//快慢指针重排链表https://leetcode.com/problems/reorder-list/https://le......
  • leetcode-1460. 通过翻转子数组使两个数组相等
    1460.通过翻转子数组使两个数组相等图床:blogimg/刷题记录/leetcode/1460/刷题代码汇总:https://www.cnblogs.com/geaming/p/16428234.html题目思路首先,这是一道“简......
  • leetcode150:逆波兰表达式求值
    packagecom.mxnet;importjava.util.Stack;publicclassSolution150{publicstaticvoidmain(String[]args){}/***根据逆波兰表示法,......
  • wwm.LeetCodeHelper C#刷题帮助类库
    wwm.LeetCodeHelper仓库地址:https://gitee.com/wwmin/www.leetcode.helper1.说明wwm.LeetCodeHelper是一款帮助在本地用C#做LeetCode题的一个库,具有自动拉取题生成c......
  • LeetCode 21 合并两个有序链表
    /***Definitionforsingly-linkedlist.*structListNode{*intval;*ListNode*next;*ListNode():val(0),next(nullptr){}*ListN......
  • 动态规划——leetcode55、跳跃游戏
    题目描述: 解题方法:动态规划动态规划解题步骤:确定状态:最后一步:如果能跳到最后一个下标,我们考虑他的最后一步到n-1(最后一个下标),这一步是从i跳过......
  • #前端算法救赎系列#LeetCode01.两数之和
    1.两数之和给定一个整数数组nums和一个整数目标值target,请你在该数组中找出和为目标值target的那两个整数,并返回它们的数组下标。示例1:输入:nums=[2,7,11,1......
  • ref 获取元素和组件
    父组件:<template><div><divclass="name"ref="oneRef">ref第一个</div><divclass="name"ref="twoRef">ref第2个</div><helloref="ziRef"......