LeetCode:658. Find K Closest Elements程序分析

好久没有练习算法了，以此纪研究生以来第一次练习算法题。
原题链接：https://leetcode.com/problems/find-k-closest-elements/description/

题目描述：大概意思是给定一个数组[1,2,3,4,5]和两个常数k，x然后在数组中找到与x最近的的k个元素，找到后的元素依旧按照升序排列。

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.

Example 1:

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

Example 2：

Input: [1,2,3,4,5], k=4, x=-1
Output: [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 10_4
Absolute value of elements in the array and x will not exceed 10_4

由于看题疏忽，没有看到给予的是排好序的数组，程序写的是排不排序都可以，因此第一次提交的程序着实运行的有些慢，在自己编译器中是可以编译通过的，但是提交上去被提示数组越界：

class Solution {
public:
    vector<int> findClosestElements(vector<int>& arr, int k, int x) {
        int temp = 0;
        vector<int> big(arr.size());
        int distance = 0;

        big[0] = arr[0];

        for(int i = 1; i < arr.size(); i ++)
        {
            if(abs(arr[i] - x) >= abs(big[i-1] - x))
                big[i] = arr[i];
            else
            {
                for(int j = i;j > 0;j --)
                {
                    if(abs(arr[i]-x) < abs(big[j-1]- x))
                    {
                        temp = big[j-1];
                        big[j-1] = arr[i];
                        big[j] = temp;
                    }
                }
            }
        }
        sort(big.begin(),big.end()+k);
        vector<int> result(big.begin(),big.begin()+k);
        return result;
    }
};

于是乎，将程序改成：

class Solution {
public:
    vector<int> findClosestElements(vector<int>& arr, int k, int x) {
        int temp = 0;
        vector<int> big(arr.size());
        int distance = 0;

        big.at(0) = arr.at(0);

        for(int i = 1; i < arr.size(); i ++)
        {
            if(abs(arr.at(i) - x) >= abs(big.at(i-1) - x))
                big.at(i) = arr.at(i);
            else
            {
                for(int j = i;j > 0;j --)
                {
                    if(abs(arr.at(i)-x) < abs(big.at(j-1)-x))
                    {
                        temp = big.at(j-1);
                        big.at(j-1) = arr.at(i);
                        big.at(j) = temp;
                    }
                }
            }
        }
        sort(big.begin(),big.begin()+k);
        vector<int> result(big.begin(),big.begin()+k);
        return result;
    }
};

继续提交，由于使用了at操作符，对数组越界进行了检查，导致程序运行速度更慢，直接的结果是提示Status: Time Limit Exceeded好吧，时间超时了，看来这个平台不仅注重时间复杂度和空间复杂度，连安全性也一并注重。
上述程序的复杂度应该是 O(n2)，确实很慢呀。

于是乎，对程序进行修改：

vector<int> findClosestElements(vector<int>& arr, int k, int x) {
    int left = 0;
    int right = arr.size()-k;
    while(left<right){
        int mid = left+(right-left)/2;
        if(x-arr[mid]>arr[mid+k]-x){
            left = mid+1;
        }else{
            right = mid;
        }
    }
    vector<int> result(arr.begin()+left, arr.begin()+left+k);
    return result;
}

这次时间复杂度为O(logn+k)