数据结构-武大933

叁歲伎倆 2022-05-17 00:58 157阅读 0赞

**2018武汉大学933**

两个整数递增有序序列 A，B 分别有 n 和 m 个元素，求第 k 大的数（1≤K≤n+m）， 要求最佳时间空间复杂度。

函数原型：int kMax(int\[\] A,int\[\] B,int k)

例子：

**输入**

A\[1,3,4,5,6\]

B\[3,4,5,6\]

k=4

**输出**

**4**

#include<iostream>
    #include<cstdio>
    #include<cstring>
    #include<cstdlib>
    #define MAX 0x3f3f3f3f
    using namespace std;
    
    int findIthValue(int a[], int n1, int b[], int n2, int k)
    {
    	/*
    		其实和归并的思想差不多，只是要在归并的过程中判断已经拍好了几个元素了而已
    		要注意的是可能有一个数组提前被遍历完成的情况，其他的都很简单 
    	*/
    	int s1= 0, s2= 0;
    	int count = 0, now = 0;
    	while(s1 < n1 && s2 < n2)
    	{
    		if(a[s1] <= b[s2])
    		{
    			now = a[s1++];
    			count++;
    		}
    		else if(a[s1] > b[s2])
    		{
    			now = b[s2++];
    			count++;
    		}
    		if(count == k)
    			return now;
    	}
    
    	while(s1 < n1)
    	{
    		now = a[s1++];
    		count++;
    		if(count == k)
    			return now;
    	}
    	while(s2 < n2)
    	{
    		now = b[s2++];
    		count++;
    		if(count == k)
    			return now;
    	}
    	
    	return MAX;
    }
    
    int main()
    {
    	
    	int a[] = {1};
    	int b[] = {3,4,6,8};
    	int result = findIthValue(a, 1, b, 4, 3);
    	cout<<"THe result is："<<result;
    	return 0;
     }

发表评论取消回复

表情：

评论列表（有 0 条评论，157人围观）

还没有评论，来说两句吧...

相关阅读

相关 Node.js运行app.js时候报错933

问题描述 `提示：在做网易云音乐小程序时，运行后端API时候报错：` 使用cmd运行node app.js报错：报错内容： node:internal/mod

拼搏现实的明天。/ 2024年04月01日 15:44/ 0 赞/ 49 阅读

相关 LeetCode（Queue)933. Number of Recent Calls

1.问题 You have a RecentCounter class which counts the number of recent requests within

男娘i/ 2023年09月25日 19:33/ 0 赞/ 46 阅读

相关 933. 最近的请求次数

题目来源 [933. 最近的请求次数][933.] 题目描述 ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_sh

叁歲伎倆/ 2023年02月11日 03:16/ 0 赞/ 12 阅读

相关 leetcode933最近请求的次数

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ub

男娘i/ 2022年10月05日 00:59/ 0 赞/ 121 阅读

相关武汉大学计算机学院曹瑀,武大计算机青协

武汉大学计算机学院青年志愿者协会第一次全体大会计算机学院青年志愿者协会　郭湘 2007年9月26日 ![a4c26d1e5885305701be709a3d33442f

今天药忘吃喽~/ 2022年08月29日 15:45/ 0 赞/ 243 阅读

相关数据结构-武大933

2018武汉大学933 两个整数递增有序序列 A，B 分别有 n 和 m 个元素，求第 k 大的数（1≤K≤n+m），要求最佳时间空间复杂度。函数原型：int kMax

叁歲伎倆/ 2022年05月17日 00:58/ 0 赞/ 158 阅读

相关一名武大同学的春招48小时

本文作者：求职锦鲤转载自“互联网大师兄带你” ![1240][] 我今年23岁，没钱，没offer，没脱单。每每面试自我介绍第一句我都说，我是一名毕业于武汉大学的

女爷i/ 2022年02月15日 13:13/ 0 赞/ 145 阅读

相关【数据结构】重新面对数据结构

对于课堂上的《数据结构》，我会怀疑学校的教育方式；对于桌面上的三本《数据结构》，我会质疑作者到底有没有站在平民百姓的角度去写这些书；对于网上的一些《数据结构》教学视频，我开始质

妖狐艹你老母/ 2021年12月16日 12:13/ 0 赞/ 360 阅读

相关【leetcode】933.最近的请求数

写一个 RecentCounter 类来计算最近的请求。它只有一个方法：ping(int t)，其中 t 代表以毫秒为单位的某个时间。返回从 3000 毫秒前到现在的

淡淡的烟草味﹌/ 2021年10月03日 02:00/ 0 赞/ 303 阅读

相关生信笔记-mooc【武大】

.DNA拓扑学在拓扑结构的限制下，DNA进行复制等过程。还有连环数=扭转数+缠绕数。 2.拓扑异构酶 DNA变性破坏了两条链之间碱基形成的氢键。和拓扑异构酶是不同的。

灰太狼/ 2021年03月28日 12:48/ 0 赞/ 595 阅读