4、LeetCode 题解 - Longest Palindromic Substring（最大回文子字符串）
2019-07-10
目录
- > 1、/null - LeetCode 题解 - Two Sum
- > 2、/null - LeetCode 题解 - Add Two Numbers
- > 3、/null - LeetCode 题解 - Longest Substring Without Repeating Characters
- > 4、/null - LeetCode 题解 - Longest Palindromic Substring（最大回文子字符串）
- > 5、/null - LeetCode 题解 - ZigZag Conversion（Z型转换）
- > 6、/null - LeetCode 题解 - Reverse Integer（翻转整数）
- > 7、/null - LeetCode 题解 - String to Integer (atoi)（转换到整型）
- > 8、/null - LeetCode 题解 - String to Integer (atoi)（转换到整型）
- > 9、/null - LeetCode 题解 - Palindrome Number（回文数）
- > 10、/null - LeetCode 题解 - Regular Expression Matching （正则表达式匹配）
- > 11、/null - LeetCode 题解 - Container With Most Water（最大水容器）
- > 12、/null - LeetCode 题解 - Integer to Roman（整型数到罗马数）
- > 13、/null - LeetCode 题解 - Roman to Integer（罗马数到整型数）
- > 14、/null - LeetCode 题解 - Longest Common Prefix（最长公共前缀）
- > 15、/null - LeetCode 题解 - 3 Sum（3 个数的和）
- > 16、/null - LeetCode 题解 - 3 Sum Closest（最接近的 3 个数的和）
- > 17、/null - LeetCode 题解 - Letter Combinations of a Phone Number（电话号码的字母组合）
- > 18、/null - LeetCode 题解 - 4 Sum（4 个数的和）
- > 19、/null - LeetCode 题解 - Remove Nth Node From End of List（从列表尾部删除第 N 个结点）
- > 20、/null - LeetCode 题解 - Valid Parentheses（有效的括号）
- > 21、/null - LeetCode 题解 - Merge Two Sorted Lists（合并两个已排序的数组）
- > 22、/null - LeetCode 题解 - Generate Parentheses（生成括号）
- > 23、/null - LeetCode 题解 - Merge k Sorted Lists（合并 K 个已排序链表）
- > 24、/null - LeetCode 题解 - Swap Nodes in Pairs（交换序列中的结点）
- > 25、/null - LeetCode 题解 - Reverse Nodes in k-Group（在K组链表中反转结点）
- > 26、/null - LeetCode 题解 - Remove Duplicates from Sorted Array（从已排序数组中移除重复元素）
- > 27、/null - LeetCode 题解 - Implement strStr()（实现 strStr() 函数）
翻译
有两个给定的排好序的数组 nums1 和 nums2，其大小分别为 m 和 n。
找出这两个已排序数组的中位数。
总运行时间的复杂度应该是 O(log(m+n))。
原文
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)).
C
public class Solution {
public double FindMedianSortedArrays(int[] nums1, int[] nums2) {
int len1=nums1.Length;
int len2=nums2.Length;
bool isEven=(nums1.Length+nums2.Length)%2==0;
int left=(len1+len2+1)/2;
int right=(len1+len2+2)/2;
if (isEven)
{
var leftValue = findKth(nums1, 0, len1 - 1, nums2, 0, len2 - 1, left);
var rightValue = findKth(nums1, 0, len1 - 1, nums2, 0, len2 - 1, right);
return (leftValue + rightValue) / 2.0;
}
else
{
return findKth(nums1, 0, len1 - 1, nums2, 0, len2 - 1, right);
}
}
public double findKth(int[] A,int lowA,int highA,int[] B,int lowB,int highB,int k)
{
if(lowA>highA)
{
return B[lowB+k-1];
}
if(lowB>highB)
{
return A[lowA+k-1];
}
int midA=(lowA+highA)/2;
int midB=(lowB+highB)/2;
if (A[midA] <= B[midB])
{
return k <= midA - lowA + midB - lowB + 1 ?
this.findKth(A, lowA, highA, B, lowB, midB - 1, k) :
this.findKth(A, midA + 1, highA, B, lowB, highB, k - (midA - lowA + 1));
}
else
{
return k <= midA - lowA + midB - lowB + 1 ?
this.findKth(A, lowA, midA - 1, B, lowB, highB, k) :
this.findKth(A, lowA, highA, B, midB + 1, highB, k - (midB - lowB + 1));
}
}
}
