链接:http://ac.jobdu.com/problem.php?pid=1004
题目描述:
Given an increasing sequence S of N integers, the median is the number at the middle position. For example, the median of S1={11, 12, 13, 14} is 12, and the median of S2={9, 10, 15, 16, 17} is 15. The median of two sequences
is defined to be the median of the non-decreasing sequence which contains all the elements of both sequences. For example, the median of S1 and S2 is 13.
Given two increasing sequences of integers, you are asked to find their median.
输入:
Each input file maycontain more thanone test case.
Each case occupies 2 lines, each gives the information of a sequence. For each sequence, the first positive integer N (≤1000000) is the size of that sequence. Then N integers follow, separated by a space.
It is guaranteed that all the integers are in the range of long int.
输出:
For each test case you should output the median of the two given sequences in a line.
样例输入:
4 11 12 13 14
5 9 10 15 16 17
样例输出:
13
趁着不忙,找点以前做过的题练练。好多算法都忘完了!九度这个平台不错,可用看自己以前的代码!
这个以前是用java做的,现在练练C。
#include <stdio.h>
#define MAX 1000000
int arr1[MAX];
int arr2[MAX];
int newArr[MAX<<1];
int main(){
int len1,len2;
while(scanf("%d", &len1) != EOF){
int i;
for(i=0; i<len1; i++)
scanf("%d",&arr1[i]);
scanf("%d", &len2);
for(i=0; i<len2; i++)
scanf("%d",&arr2[i]);
i=0;
int index=0,j=0;
while(i<len1 && j<len2){
if(arr1[i] < arr2[j])
newArr[index++] = arr1[i++];
else
newArr[index++] = arr2[j++];
}
while(i <len1)
newArr[index++] = arr1[i++];
while(j <len2)
newArr[index++] = arr2[j++];
printf("%d\n",newArr[(index-1)/2]);
}
return 0;
}
java代码:
import java.io.BufferedInputStream;
import java.util.Scanner;
public class Main {
static int arr1[];
static int arr2[];
static int arr[];
public static void main(String[] args) {
Scanner s = new Scanner(new BufferedInputStream(System.in));
while(s.hasNextInt()){
int n = s.nextInt();
arr1 = new int[n];
for(int i=0; i<n; i++)
arr1[i] = s.nextInt();
int m = s.nextInt();
arr2 = new int[m];
arr = new int[m+n];
for(int i=0; i<m; i++){
arr2[i] = s.nextInt();
}
int i=0;
int j=0;
int k=0;
while(i<n && j<m){
if(arr1[i] <arr2[j]){
arr[k++] = arr1[i++];
}
else{
arr[k++] = arr2[j++];
}
}
while(i<n)
arr[k++] = arr1[i++];
while(j<m)
arr[k++] = arr2[j++];
System.out.println(arr[(arr.length-1)/2]);
}
}
}
发现C和java的内存占用相差不大,有必要再优化下,让数组也动态生成.
优化后: 内存和时间 908 kb 10 ms
#include <stdio.h>
#include <stdlib.h>
/*#define MAX 1000000*/
// int arr1[MAX];
// int arr2[MAX];
// int newArr[MAX<<1];
int * arr1,* arr2,* newArr;
int main(){
int len1,len2;
while(scanf("%d", &len1) != EOF){
arr1 = (int *)malloc(len1*4);
int i;
for(i=0; i<len1; i++)
scanf("%d",&arr1[i]);
scanf("%d", &len2);
arr2 = (int *)malloc(len2*4);
newArr = (int *)malloc( (len1+len2)*4);
for(i=0; i<len2; i++)
scanf("%d",&arr2[i]);
i=0;
int index=0,j=0;
while(i<len1 && j<len2){
if(arr1[i] < arr2[j])
newArr[index++] = arr1[i++];
else
newArr[index++] = arr2[j++];
}
while(i <len1)
newArr[index++] = arr1[i++];
while(j <len2)
newArr[index++] = arr2[j++];
printf("%d\n",newArr[(index-1)/2]);
}
return 0;
}
分享到:
相关推荐
Given an increasing sequence S of N integers, the median is the number at the middle position. For example, the median of S1={11, 12, 13, 14} is 12, and the median of S2={9, 10, 15, 16, 17} is 15. The...
有关P-Median问题相关算法分类的综述文献
增量k-Median算法的研究与实现,张泽,卢美莲,论文针对聚类分析在动态数据方面的应用,对增量k-Median问题进行了深入研究。文中首先研究了无容量限制的增量设备选址问题,并在数�
论文研究-重力p-median模型在设施选址中的应用及检验.pdf, 区位分配模型是设施选址研究中的重要方法,其中p-median模型是应用最广泛的一种.但传统p-median模型中每一需求...
leetcode4 中位数leetcode4-中位数-
中值过滤代码matlab 使用均值和中值滤波器进行图像降噪 使用均值和中值滤波器的图像去噪Matlab代码
中值滤波代码 matlab Modified-Deciision-based-median-filter Matlab Code
按照多媒体课本上的步骤,严格执行中值区分算法,将24位图像转换为256色图
本文介绍了一种快速算法,用于计算N个样本的加权中位数(WM),该样本的线性时空复杂度与O(N log N)相对,后者是传统排序算法的时间复杂度。 Quickselect通常用于在大数据集中查找WM的一种流行选择算法是Quick...
实现了聚类算法,具有很好的参考价值,值得观看
1004 力码 去做 : array , dynamic-programming : link , math : string , sliding-window : array , median : string : string : number , reverse , bit : string : math , bit : string , match , ...
Median of Two Sorted Arrays 5 Longest Palindromic Substring 8 String to Integer 11 Container with Most Water 14 Longest Common Prefix 15 Three Sum 16 Three Sum Closest 20 Valid Parentheses 26 Remove ...
蓄水池算法 leetcode Leetcode Solutions Continue updating... lt: leetcode jz: 剑指Offer Sort & Search # Name Difficulty Solution index 1 直接插入 easy python :heart_suit: 2 简单选择排序 easy python :...
中值滤波代码 matlab improved-median-filter More details plz visit This program outcome better than inbuild medfilt2 function
"-m or -median : disable print out median price for each equity!" ;"-p or -midpoint : disable print out midpoint for each equity!" ;"-t or -transfers : disable print out transaction details for each ...
基于启发式遗传算法的带容量限制的P-median设施选址问题(在N个需求点中找出P个点建设设施满足全部需求,各点设施建设有容量限制,目标为最小化距离与对应需求量的乘积),通过轮盘法进行染色体种群进化,数据部分可...
中值过滤代码matlab 基于变异的中值滤波取证 论文的作者[1]仅出于研究目的(此方法与其他方法的评估和比较)提供了此MATLAB代码。 参考文献[1] Kang Hyeon RHEE,“使用相邻线对的变化进行中值滤波检测以进行图像...
Fast Multi-exposure Image Fusion with Median Filter and Recursive Filter, http://blog.sciencenet.cn/blog-366840-709637.html
刷leetcode不用stl wx leetcode刷题记录 刷完100题后,有了一定的基础,开始刷Top Interview Questions里的题 2019-7-16 21:57:14 除开需要订阅解锁的题目,总算是刷完了Top ...Median of Two Sorted A