http://www.leetcode.com/onlinejudge
Median of Two Sorted Arrays
代码风格很乱,将就看吧,
写完才发现,写的有问题,没必要对end做操作,只操作start就可以了,类似归并
public class testMedianofTwoSortedArrays {
/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
int A[]={};
int B[]={2,3};
double c=new testMedianofTwoSortedArrays().findMedianSortedArrays(A, B);
System.out.println(c);
}
public double findMedianSortedArrays(int A[], int B[]) {
// Start typing your Java solution below
// DO NOT write main() function
int startA=0;
int startB=0;
int tempS=0,tempE=0;
int endA=A.length-1;
int endB=B.length-1;
double result=0;
while(true){
if(startA>=A.length){
tempS=B[startB];
startB++;
}else{
if(startB>=B.length){
tempS=A[startA];
startA++;
}
}
if(startA<A.length&&startB<B.length){
if(A[startA]>B[startB]){
tempS=B[startB];
startB++;
}else{
tempS=A[startA];
startA++;
}
}
if(endA<0){
tempE=B[endB];
endB--;
}else{
if(endB<0){
tempE=A[endA];
endA--;
}
}
if(endA>=0&&endB>=0){
if(A[endA]<B[endB]){
tempE=B[endB];
endB--;
}else{
tempE=A[endA];
endA--;
}
}
if (endA<startA&&endB<startB){
break;
}
}
return ((double)tempS+tempE)/2;
}
}
改进后的,public class testMedianofTwoSortedArrays {
/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
int A[] = {};
int B[] = { 1, 2, 3, 4, 5 };
double c = new testMedianofTwoSortedArrays().findMedianSortedArrays(A,
B);
System.out.println(c);
}
public double findMedianSortedArrays(int A[], int B[]) {
// Start typing your Java solution below
// DO NOT write main() function
int startA = 0;
int startB = 0;
int tempS = 0, tempE = 0;
double end = ((double) A.length + B.length) / 2;
double result = 0;
while (startA + startB < end) {
if (startA >= A.length) {
tempS = B[startB];
startB++;
} else if (startB >= B.length) {
tempS = A[startA];
startA++;
} else if (A[startA] > B[startB]) {
tempS = B[startB];
startB++;
} else {
tempS = A[startA];
startA++;
}
}
if ((A.length + B.length) % 2 == 1) {
tempE = tempS;
} else if (startA >= A.length) {
tempE = B[startB];
} else if (startB >= B.length) {
tempE = A[startA];
} else if (A[startA] > B[startB]) {
tempE = B[startB];
} else {
tempE = A[startA];
}
return ((double) tempS + tempE) / 2;
}
}
分享到:
相关推荐
There are two sorted arrays nums1 and nums2 of size m and n respectively. ...Find the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)). Java AC版本
4. Median of Two Sorted Arrays 7. Reverse Integer 9. Palindrome Number 11. Container With Most Water 13. Roman to Integer 15. 3Sum 16. 3Sum Closest 17. Letter Combinations of a Phone Number 18. 4Sum ...
leetcode 无法登录两个有序数组的中位数 问题 有两个大小分别为 m 和 n 的排序数组 nums1 和 nums2。求两个排序数组的中位数。 整体运行时间复杂度应该是 O(log (m+n))。 您可以假设 nums1 和 nums2 不能都为空。 ...
leetcode Python 001 leetcode的算法问题 这是我的解决方案,用 cpp 、 java 和 python 编写 #LeetCode 解决的问题: 001. Two Sum 002. Add Two Numbers 003. Longest Substring Without Repeating Characters4. ...
lru缓存leetcode leetcode 1. Two Sum 2. Add Two Numbers 3. Longest Substring Without Repeating Characters 4. Median of Two Sorted Arrays 5. Longest Palindromic Substring 7. Reverse Integer 9. ...
leetcode Python 001 力码 ├── Algorithms │ ├── cpp │ │ ├── 001 - Two Sum.cpp │ │ ├── 002 - Add Two Numbers.cpp │ │ ├── 003 - Longest Substring Without Repeating ...
7 Median of Two Sorted Arrays 33 8 Kth Largest Element in an Array 35 9 Wildcard Matching 37 10 Regular Expression Matching in Java 39 11 Merge Intervals 43 12 Insert Interval 45 13 Two Sum 47 14 Two ...
leetcode 分类leetcode 问题分类 leetcode代码仓库,我的解题思路写在我的博客里: leetcode 代码库,我博客上的解题思路: mkdir 列表: 大批 #1:Two Sum #4:Median of Two Sorted Arrays 地图 #1:Two Sum #3:...
leetcode 2 Leetcode答案集 关于项目: 本项目包含本人LeetCode解题的答案,全部将由JavaScript语言进行解答。并会在每个题目的文件夹中添加相关的思路解析。 详情 # Title Solution Time Space Difficulty 1 Two ...
leetcode双人赛LeetCode 编号 题目 难度 题型 备注 Two Sum 简单 Add Two Numbers 中等 链结串列 重要 Longest Substring Without Repeating Characters 中等 字串 重要 Median of Two Sorted Arrays 困难 数学 ...
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分类LeetCodeSourceCodes###LeetCode1TowSum如果数组是有序的,O(n)的时间复杂度就可以解决了,现在是无序的,一开始要排一下序###LeetCode2MedianofTwoSortedArrays让用logn的时间复杂度,用了两个二分,...
LeetCode刷题总结 1.Two Sum 2.Add Two Numbers 3.Longest Substring Without Repeating Characters 4.Median of Two Sorted Arrays 5.Longest Palindromic Substring (Manacher算法待完成) 6.ZigZag Conversion 7....
leetcode题库 LeetCode-Go 理论基础 见Note 脑图 TODO 待填充 算法题 面试高频出现,以及一些非常经典重要的算法题优先 题目列表 No Title Link Solution Acceptance Difficulty Topics Solution 0001 Two Sum 46.1%...
分割数组求最大差值leetcode LeetCode 学习之路 记录自己完成LeetCode的代码和结果。 序号 中文名称 英文名称 通过率 难度 1 Two Sum 47.0% 简单 2 Add Two Numbers 36.0% 中等 3 Longest Substring Without ...
Leetcode回文串拼接 leetcode_node 题解 该项目主要用于基于Leetcode的刷题记录,与日常学习,对Leetcode上的题目按照解题方法进行分明别类的整理。 题目列表 1.Two Sum 2.Add Two Numbers 3.Longest Substring ...
Median of Two Sorted Arrays (寻找两个有序数组的中位数) Hard Divide and Conquer 5 Longest Palindromic Substring (最长回文子串) Medium Dynamic Programming 7 Reverse Integer (整数反转) Easy Math 8 String...
Median of Two Sorted Arrays 递归实现find kth 6 Longest Consecutive Sequence 7 Two Sum Hash,夹逼均可 8 3Sum Hash法转换2sum 9 3Sum Closest Sort +夹逼法 10 4Sum Sort +夹逼法 11 Remove Element 12 Next ...
leetcode题库 LeetCode 题解合集 本仓库展示了LeetCode题库中部分题目的解法(持续更新),所有代码均采用C++编写并配有输入输出样例 代码清单如下: 序号 题目 程序源码 1 两数之和 Two Sum.cpp 2 两数相加 Add Two...
4.Median of Two Sorted Arrays 7.Reverse Integer 8.String to Integer (atoi) 9.Palindrome Number 11.Container With Most Water 14.Longest Common Prefix 15.3Sum 16.3Sum Closest 19.Remove Nth Node From End...