973. 最接近原点的 K 个点-k数组维护+二分查找

973. 最接近原点的 K 个点-k数组维护+二分查找

给定一个数组 points ，其中 points[i] = [xi, yi] 表示 X-Y 平面上的一个点，并且是一个整数 k ，返回离原点 (0,0) 最近的 k 个点。

这里，平面上两点之间的距离是 欧几里德距离（ √(x1 - x2)2 + (y1 - y2)2 ）。

你可以按 任何顺序 返回答案。除了点坐标的顺序之外，答案 确保 是 唯一 的。

示例 1：

输入：points = [[1,3],[-2,2]], k = 1
输出：[[-2,2]]
解释：
(1, 3) 和原点之间的距离为 sqrt(10)，
(-2, 2) 和原点之间的距离为 sqrt(8)，
由于 sqrt(8) < sqrt(10)，(-2, 2) 离原点更近。
我们只需要距离原点最近的 K = 1 个点，所以答案就是 [[-2,2]]。

示例 2：

输入：points = [[3,3],[5,-1],[-2,4]], k = 2
输出：[[3,3],[-2,4]]
（答案 [[-2,4],[3,3]] 也会被接受。）

对于这题我们维护了一个数组长度为K得数组

/**
 * Return an array of arrays of size *returnSize.
 * The sizes of the arrays are returned as *returnColumnSizes array.
 * Note: Both indexned array and *columnSizes array must be malloced, assume caller calls free().
 */
 int find_index(int *a,int size,int v){
     int high=size-1;
     int low=0;
    if(a[size-1]<=v){
        return -1;
    }
    else{
      
      while(low<=high){
          int mid=(high+low)/2;
          if(a[mid]>v){
            high=mid-1;
          }
          else{
            low=mid+1;
          }

      }
      return low;
    }
    
 }
int** kClosest(int** points, int pointsSize, int* pointsColSize, int k, int* returnSize, int** returnColumnSizes) {
    int **a=(int **)malloc(sizeof(int*)*k);
    int  min_index[k];
    int index_record[k];
   
      *returnColumnSizes = malloc(sizeof(int) * k);
    for(int i=0;i<k;i++){
        a[i]=(int *)malloc(sizeof(int)*2);
    }
    for(int i=0;i<k;i++){
      
        (*returnColumnSizes)[i] = 2;
    }
    for(int i=0;i<k;i++){
        int z=points[i][0]*points[i][0]+points[i][1]*points[i][1];
        min_index[i]=points[i][0]*points[i][0]+points[i][1]*points[i][1];
     //   printf("z %d ",z);
       index_record[i]=i;
        if(i==0){
             
            continue;
        }
        else{
            int j=i-1;
            for(;j>=0;j--){
                if(min_index[j]>z){
                     min_index[j+1]=min_index[j];
                    index_record[j+1]=index_record[j];
                }
                    else{
                        
                         break;
                    }
            }
           // printf("-- %d ",j);
          
          
            if(j!=0){
                 min_index[j+1]=z;
                index_record[j+1]=i;

            }
            if(j==0){
                if(min_index[j]>z){
                     min_index[0]=z;
                     index_record[0]=i;
                }
                else{
                     min_index[j+1]=z;
                  index_record[j+1]=i;
                }

            }
          //  printf("j %d",j);
           

        }
    //       for(int iz=0;iz<i;iz++){
      
    //     printf("*%d ",min_index[iz]);

    //  }
    //  printf("\n");
    }
   
    for(int i=k;i<pointsSize;i++){
        int v=points[i][0]*points[i][0]+points[i][1]*points[i][1];
        int find_index_min=find_index(min_index,k,v);
        // printf(" find_index_min %d ",find_index_min);
        if(find_index_min==-1){
            continue;
        }
        else{
             for(int j=k-1;j>find_index_min;j--){
                    min_index[j]=min_index[j-1];
                     index_record[j]=index_record[j-1];
            }
            min_index[find_index_min]=points[i][0]*points[i][0]+points[i][1]*points[i][1];
            index_record[find_index_min]=i;
        }

    }
    for(int i=0;i<k;i++){
    
              a[i][0]=points[index_record[i]][0];
                a[i][1]=points[index_record[i]][1];

    }

    *returnSize=k;
    return a;
}

其运行情况如下：
在这里插入图片描述

当然上面这个方法是很粗糙的，而且有多余的内存消耗,博主发现，内存还可以优化，下面是优化后的代码：

/**
 * Return an array of arrays of size *returnSize.
 * The sizes of the arrays are returned as *returnColumnSizes array.
 * Note: Both indexned array and *columnSizes array must be malloced, assume caller calls free().
 */
 int find_index(int *a,int size,int v){
     int high=size-1;
     int low=0;
    if(a[size-1]<=v){
        return -1;
    }
    else{
      
      while(low<=high){
          int mid=(high+low)/2;
          if(a[mid]>v){
            high=mid-1;
          }
          else{
            low=mid+1;
          }

      }
      return low;
    }
    
 }
int** kClosest(int** points, int pointsSize, int* pointsColSize, int k, int* returnSize, int** returnColumnSizes) {
    int  min_index[k];
   
   
      *returnColumnSizes = malloc(sizeof(int) * k);

    for(int i=0;i<k;i++){
      
        (*returnColumnSizes)[i] = 2;
    }
    for(int i=0;i<k;i++){
        int z=points[i][0]*points[i][0]+points[i][1]*points[i][1];
        min_index[i]=points[i][0]*points[i][0]+points[i][1]*points[i][1];
     //   printf("z %d ",z);
       int x=points[i][0];
       int y=points[i][1];
        if(i==0){
             
            continue;
        }
        else{
            int j=i-1;
            for(;j>=0;j--){
                if(min_index[j]>z){
                     min_index[j+1]=min_index[j];
                 
                    points[j+1][0]=points[j][0];
                    points[j+1][1]=points[j][1];

                }
                    else{
                        
                         break;
                    }
            }
           // printf("-- %d ",j);
          
          
            if(j!=0){
                points[j+1][0]=x;
                points[j+1][1]=y;
                 min_index[j+1]=z;
              

            }
            if(j==0){
                if(min_index[j]>z){
                     min_index[0]=z;
                  
                      points[0][0]=x;
                    points[0][1]=y;
                }
                else{
                     min_index[j+1]=z;
                 
                     points[j+1][0]=x;
                points[j+1][1]=y;
                }

            }
          //  printf("j %d",j);
           

        }
    //       for(int iz=0;iz<i;iz++){
      
    //     printf("*%d ",min_index[iz]);

    //  }
    //  printf("\n");
    }
   
    for(int i=k;i<pointsSize;i++){
        int v=points[i][0]*points[i][0]+points[i][1]*points[i][1];
        int find_index_min=find_index(min_index,k,v);
        // printf(" find_index_min %d ",find_index_min);
        if(find_index_min==-1){
            continue;
        }
        else{
             for(int j=k-1;j>find_index_min;j--){
                    min_index[j]=min_index[j-1];
                  
                       points[j][0]=points[j-1][0];
                     points[j][1]=points[j-1][1];
                     
            }
            min_index[find_index_min]=points[i][0]*points[i][0]+points[i][1]*points[i][1];
           
            points[find_index_min][0]=points[i][0];
          points[find_index_min][1]=points[i][1];
        }

    }

    *returnSize=k;
    return points;
}

这个运行情况要多好了：
在这里插入图片描述

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：/a/766005.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

Linux修炼之路之进程概念，fork函数，进程状态

Linux修炼之路之进程概念，fork函数，进程状态

目录 一&#xff1a;进程概念 二&#xff1a;Linux中的进程概念 三&#xff1a;用getpid(),getppid()获取该进程的PID,PPID 四&#xff1a;用fork()来创建子进程 五&#xff1a;操作系统学科的进程状态 六&#xff1a;Linux中的进程状态 接下来的日子会顺顺利利&#xf…
阅读更多...
【MySQL备份】Percona XtraBackup加密备份实战篇

【MySQL备份】Percona XtraBackup加密备份实战篇

目录 1.前言 2.准备工作 2.1.环境信息 2.2.配置/etc/my.cnf文件 2.3.授予root用户BACKUP_ADMIN权限 2.4.生成加密密钥 2.5.配置加密密钥文件 3.加密备份 4.优化加密过程 5.解密加密备份 6.准备加密备份 7.恢复加密备份 7.1.使用rsync进行恢复 7.2.使用xtrabackup命令恢…
阅读更多...
crewAI实践过程中，memory规避openai的使用方法以及（windows下xinferece框架使用踩过的坑）

crewAI实践过程中，memory规避openai的使用方法以及（windows下xinferece框架使用踩过的坑）

问题&#xff1a; 在使用crewAI开发项目的过程中&#xff0c;memory开启后报错&#xff1a;openai key is fake 经代码核查&#xff0c;其默认使用了openai的embedding模型。 解决方法 经查阅资料&#xff0c;可以参考其本地部署llm的方法。 本地部署模型可以使用xinference…
阅读更多...
人工智能导论速成笔记

人工智能导论速成笔记

文章目录 前言考试题型第一章、人工智能导引 (10分 )课后习题第二章、Python基础 (10分 )*文件读写NumPy的使用Python绘图基础第三章、机器学习初步(15分 )逻辑回归分类(Logistic Regression)*，3.5线性回归预测(Linear Regression)*，3.6 、3.7、 3.8聚类 3.9第四章、自然语言…
阅读更多...
【信息系统项目管理师】常见图表

【信息系统项目管理师】常见图表

作文里面的画图题用语言描述画图过程 合同 采购综合评分标准 责任分配矩阵 成本预算表 成本估算 成本管理计划 活动清单 活动属性 变更日志 问题日志 项目章程 自己再添加更多内容 甘特图 甘特图包含以下三个含义&#xff1a; 1、以图形或表格的形式显示活动&#xff1b; 2、…
阅读更多...
uniapp封装虚拟列表滚动组件

uniapp封装虚拟列表滚动组件

uniapp封装虚拟列表滚动组件 这里用到一个列表&#xff0c;然后数据可能有很多很多…&#xff0c;一次性全部渲染到dom上会卡顿&#xff0c;很废性能&#xff0c;于是用了这个虚拟列表就变丝滑很多很多。 组件mosoweInventedList 代码&#xff1a; <!-- 虚拟滚动列表组件&a…
阅读更多...
常见VPS主机术语有哪些？VPS术语解析

常见VPS主机术语有哪些？VPS术语解析

常见VPS主机术语有哪些&#xff1f;本期为大家解析一下我们常见到的听到的VPS专业术语&#xff0c;帮助大家更轻松的了解VPS主机相关知识。 常见VPS主机术语 Apache – 世界上最流行的 Web 服务器软件。 CentOS – 旨在提供基于 Red Hat Enterprise Linux 的企业级操作系统的…
阅读更多...
常微分方程算法之编程示例七-两点混合边值问题（打靶法）

常微分方程算法之编程示例七-两点混合边值问题（打靶法）

目录 一、研究问题 二、C++代码 三、计算结果 一、研究问题 本节我们采用打靶法求解两点混合边值问题，打靶法的原理及推导思路请参考： 常微分方程算法之“两点边值问题”求解-CSDN博客https://blog.csdn.net/L_peanut/article/details/137449287 研究问题为
阅读更多...
学习笔记（linux高级编程）9

学习笔记（linux高级编程）9

void pthread_cleanup_push(void (*routine)(void *)&#xff0c; void *arg); 功能&#xff1a;注册一个线程清理函数 参数&#xff0c;routine&#xff0c;线程清理函数的入口 arg&#xff0c;清理函数的参数。 返回值&#xff0c;无 void pthread_cleanup_pop(int execute)…
阅读更多...
Node.js学习（一）

Node.js学习（一）

Node.js安装与入门案例&#xff1a; 需求&#xff1a;点击按钮&#xff0c;请求本地目录指定文件的内容&#xff0c;并显示在页面上 刚入门肯定想着直接写相对路径请求指定路径数据就行了&#xff0c;可是会发现不行。 网页运行在浏览器端&#xff0c;通常后续要发布&#xf…
阅读更多...
大模型应用开发实战基础

大模型应用开发实战基础

大模型应用开发实战基础 1. 背景 大模型如日中天&#xff0c;各行各业都受它影响&#xff0c;但是作为程序员&#xff0c;除了让它翻译代码不知道用它干什么&#xff0c;就像是拿着锤子的木匠&#xff0c;找不到钉子在哪。一边听着别人说2024是AI元年&#xff0c;一边又不知所…
阅读更多...
数组-二分查找

数组-二分查找

二分查找 leetcode704 /*** param {number[]} nums* param {number} target* return {number}*/ var search function(nums, target) {let left 0, right nums.length - 1;while (left < right) {const mid Math.floor((right - left) / 2) left;const num nums[mid]…
阅读更多...
【antd + vue】表格行合并，同时使用插槽

【antd + vue】表格行合并，同时使用插槽

一、需求说明 表格中&#xff0c;如果一个学校有多个考试科目&#xff0c;则分行展示&#xff0c;其余列&#xff0c;则合并为一行展示&#xff0c;如图所示 二、需求分析 1、表格行合并 相当于有4行&#xff0c;其中1、2行是同一个学校包含不同考试科目及对应人次的数据&am…
阅读更多...
生成式AI赋能金融信贷：减少信用评分偏差

生成式AI赋能金融信贷：减少信用评分偏差

信用评分在确定谁获得信贷以及以何种条件获得信贷方面发挥着关键作用。然而&#xff0c;尽管这一点很重要&#xff0c;但传统的信用评分系统长期以来一直受到一系列关键问题的困扰——从偏见和歧视&#xff0c;到有限的数据考虑和可扩展性挑战。例如&#xff0c;一项针对美国贷…
阅读更多...
1:25万基础电子地图（西藏版）

1:25万基础电子地图（西藏版）

我们为你分享过四川版、云南版、江西版、贵州版、重庆版和青海版的1比25万基础电子地图&#xff0c;现在再为你分享西藏版的电子地图。 如果你需要西藏版的1比25万基础电子地图&#xff0c;你可以在文末查看该数据的领取方法。 基础电子地图西藏版 西藏版1:25万基础电子地图…
阅读更多...
Xilinx FPGA:vivado利用单端RAM/串口传输数据实现自定义私有协议

Xilinx FPGA:vivado利用单端RAM/串口传输数据实现自定义私有协议

一、项目要求 实现自定义私有协议&#xff0c;如&#xff1a;pc端产生数据&#xff1a;02 56 38 &#xff0c;“02”代表要发送数据的个数&#xff0c;“56”“38”需要写进RAM中。当按键信号到来时&#xff0c;将“56”“38”读出返回给PC端。 二、信号流向图 三、状态…
阅读更多...
FVCOM水环境、污染物迁移、水交换、水质、潮流、温盐、波浪及泥沙数值模拟

FVCOM水环境、污染物迁移、水交换、水质、潮流、温盐、波浪及泥沙数值模拟

原文链接&#xff1a;FVCOM水环境、污染物迁移、水交换、水质、潮流、温盐、波浪及泥沙数值模拟https://mp.weixin.qq.com/s?__bizMzUzNTczMDMxMg&mid2247607618&idx2&sn5132fb8bfcbd02c2be308f6c6304c6d2&chksmfa8264a5cdf5edb3226d1b0597bb6c39f867601b961b…
阅读更多...
[开源软件] 支持链接汇总

[开源软件] 支持链接汇总

“Common rules: 1- If the repo is on github, the support/bug link is also on the github with issues”" label; 2- Could ask questions by email list;" 3rd party software support link Note gcc https://gcc.gnu.org openssh https://bugzilla.mindrot.o…
阅读更多...
Web3 ETF 的软件开发框架

Web3 ETF 的软件开发框架

Web3 ETF 的软件开发框架主要包含以下几个方面&#xff0c;需要说明的是&#xff0c;Web3 ETF 仍处于早期发展阶段&#xff0c;相关技术和标准尚未成熟。在开发 Web3 ETF 时&#xff0c;需要谨慎评估风险&#xff0c;并做好安全防范措施。北京木奇移动技术有限公司&#xff0c;…
阅读更多...
解决卡顿发热，超帧技术焕发中重载游戏动力

解决卡顿发热，超帧技术焕发中重载游戏动力

近几年&#xff0c;中国手游市场规模不断扩大&#xff0c;开发者通过在画面、玩法等方面的持续创新和打磨&#xff0c;推出更加精品化的产品。然而愈发精美的画质和复杂的玩法&#xff0c;也给硬件带来超高的负载&#xff0c;导致玩家在游戏过程中&#xff0c;频繁出现掉帧卡顿…
阅读更多...
最新文章

Copyright @ 2022~2023