C++STL中vector使用策略(二)

下面来看一道LeetCode上的困难题——两个排序数组的中位数

       这道题只要掌握了vector的基本用法以及常用的成员函数,做起来不难,就是要细心

       首先利用push_back函数,将nums2依次插入到nums1尾部,然后利用sort(nums1.begin(),nums2.end())函数将合并后的元素进行排序。最后利用size()判断其元素个数是偶数还是奇数,以此决定输出中间两位数的平均数还是中间的数。下面给出AC代码

class Solution {
public:
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2)
    {
        for(int its = 0;its < nums2.size();++its)
        {
            nums1.push_back(nums2.at(its));
        }
        sort(nums1.begin(),nums1.end());
        if(nums1.size() % 2 == 0)
        {
            return (double)(nums1.at((nums1.size()/2) - 1) + nums1.at(nums1.size()/2))/2;
        }
        else
        {
            return nums1.at(((nums1.size())/2));
        }
    }
};

       再看一道题——打印锯齿矩阵

       锯齿矩阵是指每一行包含的元素个数不相同的矩阵,比如:

3 5 2 6 1
2 3 4
1 6 2 7

读入若干对整数(x,y),表示在第x行的末尾加上一个元素y。输出最终的锯齿数组。初始时矩阵为空。

输入格式

第一行输入两个整数(1≤n,m≤10000),其中 n表示锯齿数组的行数,m表示插入的元素总数。接下来一共 mm 行,每行两个整数x,y(1≤x≤n,0≤y≤10000),表示在第 x行的末尾插入一个元素 y。

输出格式

一共输出 n 行,每行若干个用空格分隔的整数。如果某行没有任何元素,则输出一个空行

样例输入

3 12
1 3
2 2
2 3
2 4
3 1
3 6
1 5
1 2
1 6
3 2
3 7
1 1

样例输出

3 5 2 6 1
2 3 4
1 6 2 7

这题刚开始一看可能感觉需要用二维vector向量,vector<vector <int> >vec,但是其实一个vector<int> vec[1000]就能满足这题的要求了,但是要先分清楚这几个的区别

vector<vector<int> >vec;//vector里面每个元素都是vector,相当于二维vector
vector<int>vec[1000];//开一个1000的数组,里面每个元素是一个vector
vector<int>vec(1000);//开一个vector,大小1000

剩下的代码也就很简单了

#include <bits/stdc++.h>
using namespace std;
int main()
{
	vector<int> vec[10005];
	int i,j,n,m,tmp,ans = 0,x,y;
	cin>>n>>m;
	for(i = 0;i < m;i++)
	{
		cin>>x>>y;
		vec[x].push_back(y);
	}		
	for(int i = 1;i <= n;i++)
	{
		for(j = 0;j < vec[i].size();j++)
		{
			if(j != vec[i].size() - 1)
			{
				cout<<vec[i][j]<<" "; 
			}
			else
			{
				cout<<vec[i][j];
			}
		}
		if(i < n)
		{
			cout<<endl;
		}
	}
	return 0;	 
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏TensorFlow从0到N

讨厌算法的程序员 5 - 合并算法

本篇介绍的“合并”算法,是为后面学习“归并排序”的一个准备。合并算法是归并排序中的一个子算法,请注意两者之间的关系和差异。 之所以把它独立成一篇,一方面是一旦...

3375
来自专栏人工智能LeadAI

讨厌算法的程序员 | 第五章 合并算法

本篇介绍的“合并”算法,是为后面学习“归并排序”的一个准备。合并算法是归并排序中的一个子算法,请注意两者之间的关系和差异。 之所以把它独立成一篇,一方面是一旦了...

3555
来自专栏前端儿

A+B Problem(V)

做了A+B Problem之后,Yougth感觉太简单了,于是他想让你求出两个数反转后相加的值。帮帮他吧

671
来自专栏有趣的Python

9-玩转数据结构-线段树

上一章我们介绍了堆,这一章我们介绍一种新的树结构,线段树(区间树) Segment Tree

1944
来自专栏灯塔大数据

每周学点大数据 | No.22 外排序

No.22期 外排序(一) Mr. 王:接下来我们看一看在磁盘算法中一个比较典型的例子——外排序。 小可:那什么又是外排序呢? Mr. 王:外排序是相...

3506
来自专栏用户2442861的专栏

对vector等STL标准容器进行排序操作

STL几乎封装了所有的数据结构中的算法,从链表到队列,从向量到堆栈,对hash到二叉树,从搜索到排序,从增加到删除......可以说,如果你理解了STL,你会...

1492
来自专栏架构之路

一条直线上N个线段所覆盖的总长度

转自http://blog.csdn.net/bxyill/article/details/8962832 问题描述: 现有一直线,从原点到无穷大。 这条直线上...

3375
来自专栏技术碎碎念

递归与分治之快速排序

分治法就是把一个大问题分解为多个类型相同的子问题,最后把这些子问题的解合并起来就是问题的解。 快速排序(Quicksort)是对冒泡排序的一种改进,采用了分治的...

2786
来自专栏mathor

BFPRT算法

 首先将原数组分成5个一组,每组内进行排序,组间不排序,然后将每组的中位数取出再次进行上述操作,直到最后只能分成一组了,然后取出中位数,将这个中位数当作标尺进行...

682
来自专栏WD学习记录

LeetCode Median of Two Sorted Arrays

There are two sorted arrays nums1 and nums2 of size m and n respectively.

791

扫码关注云+社区