数据结构-武大933

叁歲伎倆 2022-05-17 00:58 142阅读 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 条评论，142人围观）

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

相关阅读

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

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

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

相关 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 赞/ 33 阅读

相关 leetcode933最近请求的次数

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

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

相关数据结构-武大933

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

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

相关【数据结构】数据的存储结构

数据有有线性结构、树形结构、图状结构和集合四种逻辑结构，那么它们是如何存储的呢？数据结构的存储结构有两种，分别是顺序存储和链式存储。顺序存储的特点是借助元素在存储器中的相对

小咪咪/ 2022年05月09日 17:14/ 0 赞/ 320 阅读

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

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

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

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

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

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

相关数据结构：数据结构三要素

三要素：数据的逻辑结构：可以理解为我们看到的程序的样子，比如程序先后做了哪些操作，一个数组里面按照什么样的规律存放了哪些数据等。这是比较直观的。 ![wate

约定不等于承诺〃/ 2021年12月09日 18:43/ 0 赞/ 389 阅读

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

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

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

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

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

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