• C练题笔记之:Leetcode-658. 找到 K 个最接近的元素


    题目:

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

    整数 a 比整数 b 更接近 x 需要满足:

    |a - x| < |b - x| 或者
    |a - x| == |b - x| 且 a < b
     

    示例 1:

    输入:arr = [1,2,3,4,5], k = 4, x = 3
    输出:[1,2,3,4]
    示例 2:

    输入:arr = [1,2,3,4,5], k = 4, x = -1
    输出:[1,2,3,4]
     

    提示:

    1 <= k <= arr.length
    1 <= arr.length <= 104
    arr 按 升序 排列
    -104 <= arr[i], x <= 104

    来源:力扣(LeetCode
    链接:https://leetcode.cn/problems/find-k-closest-elements
    著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

    结果:

    解题思路:

    首先找到数组中最靠近x的值。因为后面是计算开始的值,start是记录left的,所以这里如果没有等于x的,则取比x大一个的那个值。

    这样,下一个循环的时候,如果比x小的最大的那个值距离x更近,则会start 左移。始终保持start的位置是我们要记录的最开始的位置。

    最后就按照start的位置开始k个数值都放到返回数组里就好了。

    代码:

    1. /**
    2. * Note: The returned array must be malloced, assume caller calls free().
    3. */
    4. int* findClosestElements(int* arr, int arrSize, int k, int x, int* returnSize){
    5. int *retArr = (int *)malloc(sizeof(int) * k);
    6. * returnSize = k;
    7. // 找到最接近x的值,如果没有==x的,就取第一个比x大的值
    8. int mid = 0;
    9. for (; mid < arrSize - 1; mid++) {
    10. if (arr[mid] == x) {
    11. break;
    12. } else if (arr[mid] < x && arr[mid + 1] > x) {
    13. mid++;
    14. break;
    15. } else if (arr[mid] > x) {
    16. break;
    17. }
    18. }
    19. int right, left;
    20. if (mid == 0) {
    21. left = mid;
    22. right = mid + 1;
    23. } else {
    24. left = mid - 1;
    25. right = mid;
    26. }
    27. // 通过循环找到需要我们记录的连续数据的最开始那个下标
    28. int start = mid;
    29. for (int i = 0; i < k; i ++) {
    30. if (left < 0) {
    31. break;
    32. } else if (right >= arrSize) {
    33. start = left--;
    34. } else if(left >= 0 && abs(arr[left] - x) < abs(arr[right] - x)) {
    35. start = left--;
    36. } else if (arr[left] < arr[right] && abs(arr[left] - x) == abs(arr[right] - x)) {
    37. start = left--;
    38. } else {
    39. right++;
    40. }
    41. }
    42. for (int i = 0; i < k; i++) {
    43. retArr[i] = arr[start + i];
    44. }
    45. return retArr;
    46. }

  • 相关阅读:
    Fortify白盒神器20.1.1下载及安装(非百度网盘)
    C# 设置PDF表单不可编辑、或提取PDF表单数据
    压缩与解压 .tar .tar.gz .tar.bz2 解压 tar.xz
    MindSpore静态图模式下如何实现获取网络中间层的输出
    【Vue】VueCLI 的使用和单文件组件(1)
    (二)Python类型总结
    数据结构算法-回溯算法
    Bun v0.8.0 正式发布,Zig 编写的 JavaScript 运行时
    购物H5商城架构运维之路
    vite2 + vue3 使用svg图标
  • 原文地址:https://blog.csdn.net/lingjinyue/article/details/126552103