LeetCode题目记录-658. 找到 K 个最接近的元素(C++代码实现)

实现思路：见代码注释。

class Solution {
public:
    vector findClosestElements(vector& arr, int k, int x) {
        int n = arr.size();
        vector res;


        
        //实现寻找数组中的k的位置
        int kIndex = -1;

        for(int i = 0;i < n;i++){
            if(arr[i] == x) {
                kIndex = i;
                break;
            }
        }

        //设置的int findFlag = 0;表示数组最小和最大值之间是否存在该元素
        int findFlag = 1;//1表示存在

        if(kIndex == -1){//数组中不存在该元素

            //表示数组中没有找到对应的元素
            if(x < arr[0]){//表示x小于arr数组的最左边元素
                for(int i = 0;i < k;i++){//那么从0开始输出k个数即可
                    res.push_back(arr[i]);
                }
                sort(res.begin(),res.end());
                return res;
            }else if(x > arr[n - 1]){//表示x大于arr数组的最右边元素
                for(int i = n - 1;i >= n - k;i --){//那么倒序输出数组中的k个数即可
                    res.push_back(arr[i]);
                }
                sort(res.begin(),res.end());
                return res;
            }else{
                //表示该元素只是单纯地没有出现在arr数组中且其大小在数组的最大和最小值之间
                //这种情况下，寻找到第一个大于x的元素，并将其index作为kIndex
                for(int i = 0;i < n;i ++){
                    if(arr[i] > x){
                        kIndex = i;
                        break;
                    }
                }
            }

            //对于该x元素大小值在数组的最大和最小值之间的情况进行操作
            //由于数组元素应当出现在该kIndex位置的前后两个元素中间
            //所以首先确定left指针的范围
            int lbegin = kIndex - k;
            if(lbegin < 0){
                lbegin = 0;//如果左边可能范围的开始位置小于0表示左边最少从0开始
            }

            //确定右边指针的范围
            int rend = kIndex + k - 1;
            if(rend > n - 1){
                rend = n - 1;//如果右边的范围结束位置大于n - 1，那么表示右边最大到n - 1
            }

            //while循环返回其中最接近的数
            int left = kIndex - 1;
            int right = kIndex;

            while(left >= lbegin && right <= rend){
                if((abs(arr[left] - x) < abs(arr[right] - x)) || (abs(arr[left] - x) == abs(arr[right] - x) && arr[left] < arr[right])){
                    //表示左边指针和x的差距小于右边指针，那么将左边指针指向的元素放入到res数组中
                    res.push_back(arr[left]);
                    //然后左边指针减1
                    left --;
                    //计数变量k减1
                    k--;
                    //判断k是否为0，是的话跳出循环
                    if(k == 0) break;
                }else{//如果上述两种情况都不满足，那么将右指针对应的元素放到res中去
                    res.push_back(arr[right]);
                    right++;
                    k--;
                    if(k == 0) break;
                }
            }

            if(k != 0 && right == rend + 1){//表示右指针已经到头了，那么将左指针的元素继续增加到res中
                while(left >= lbegin){
                    res.push_back(arr[left]);
                    left--;
                    k--;
                    if(k == 0) break;
                }
            }else if(k != 0 && left == lbegin - 1){
                while(right <= rend){
                    res.push_back(arr[right]);
                    right ++;
                    k--;
                    if(k == 0) break;
                }
            }

            sort(res.begin(),res.end());

        }else{//表示数组中存在该元素

            //由于数组可能出现在该kIndex位置的前后k个元素
            //所以首先确定left指针的范围
            int lbegin = kIndex - k + 1;
            if(lbegin < 0){
                lbegin = 0;//如果左边可能范围的开始位置小于0表示左边最少从0开始
            }

            //确定右边指针的范围
            int rend = kIndex + k - 1;
            if(rend > n - 1){
                rend = n - 1;//如果右边的范围结束位置大于n - 1，那么表示右边最大到n - 1
            }

            //while循环返回其中最接近的数
            int left = kIndex - 1;
            int right = kIndex + 1;

            k --;
            res.push_back(x);

            while(left >= lbegin && right <= rend){
                if((abs(arr[left] - x) < abs(arr[right] - x)) || (abs(arr[left] - x) == abs(arr[right] - x) && arr[left] < arr[right])){
                    //表示左边指针和x的差距小于右边指针，那么将左边指针指向的元素放入到res数组中
                    res.push_back(arr[left]);
                    //然后左边指针减1
                    left --;
                    //计数变量k减1
                    k--;
                    //判断k是否为0，是的话跳出循环
                    if(k == 0) break;
                }else{//如果上述两种情况都不满足，那么将右指针对应的元素放到res中去
                    res.push_back(arr[right]);
                    right++;
                    k--;
                    if(k == 0) break;
                }
            }

            if(k != 0 && right == rend + 1){//表示右指针已经到头了，那么将左指针的元素继续增加到res中
                while(left >= lbegin){
                    res.push_back(arr[left]);
                    left--;
                    k--;
                    if(k == 0) break;
                }
            }else if(k != 0 && left == lbegin - 1){
                while(right <= rend){
                    res.push_back(arr[right]);
                    right ++;
                    k--;
                    if(k == 0) break;
                }
            }
            sort(res.begin(),res.end());
        }

        

        return res; 
    }
};

AC截图：