Movatterモバイル変換

[0]ホーム
URL:

Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

 Sign up
Appearance settings

Commitab36498

Browse files
committed
feat: add 004
1 parent148e371 commitab36498

File tree

8 files changed

+601
-202
lines changed

8 files changed

+601
-202
lines changed

‎README.md

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -56,7 +56,7 @@
5656

5757
|#|Title|Tag|
5858
|:-------------|:-------------|:-------------|
59-
|4|Median of Two Sorted Arrays|Binary Search, Array, Divide and Conquer|
59+
|4|[Median of Two Sorted Arrays][004]|Array,Binary Search, Divide and Conquer|
6060

6161

6262

‎note/004/README.md

Lines changed: 70 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,70 @@
1+
#[Median of Two Sorted Arrays][title]
2+
3+
##Description
4+
5+
There are two sorted arrays**nums1** and**nums2** of size m and n respectively.
6+
7+
Find the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)).
8+
9+
**Example 1:**
10+
11+
```
12+
nums1 = [1, 3]
13+
nums2 = [2]
14+
15+
The median is 2.0
16+
17+
```
18+
19+
**Example 2:**
20+
21+
```
22+
nums1 = [1, 2]
23+
nums2 = [3, 4]
24+
25+
The median is (2 + 3)/2 = 2.5
26+
```
27+
28+
**Tags:** Array, Binary Search, Divide and Conquer
29+
30+
31+
##思路
32+
33+
题意是给你两个已排序的递增数组，让你找出其中位数，乍一看这题并不是很难，其实这题难度不可小觑，要做出时间复杂度为O(log (m+n))的话需要了解从两个递增数组中找出第k大的元素，也就是我写的`helper`函数所起到的作用。下面来解释以下其原理：假设数组分别记为A，B，当前需要搜索第k大的数，于是我们可以考虑从数组A中取出前m个元素，从数组B中取出k-m个元素。由于数组A，B分别排序，则A[m]大于从数组A中取出的其他所有元素，B[k-m] 大于数组B中取出的其他所有元素。此时，尽管取出元素之间的相对大小关系不确定，但A[m]与B[k-m]的较大者一定是这k个元素中最大的。那么，较小的那个元素一定不是第k大的，它至多是第k-1大的：因为它小于其他未被取出的所有元素，并且小于取出的k个元素中最大的那个。为叙述方便，假设A[m]是较小的那个元素。那么，我们可以进一步说，A[1], A[2]…A[m-1]也一定不是第k大的元素，因为它们小于A[m]，而A[m]至多是第k-1大的。因此，我们可以把较小元素所在数组中选出的所有元素统统排除，并且相应地减少k值。这样，我们就完成了一次范围缩小。特别地，我们可以选取m=k/2。而本题只是其一种情况而已，也就当总长为偶数时，找出其中间的两个数，相加除二即可；当总长为奇数时，找到中间的数即可。
34+
35+
```java
36+
classSolution {
37+
publicdoublefindMedianSortedArrays(int[]nums1,int[]nums2) {
38+
int len= nums1.length+ nums2.length;
39+
if (len%2==0) {
40+
return (helper(nums1,0, nums2,0, len/2)+ helper(nums1,0, nums2,0, len/2+1))/2.0;
41+
}
42+
return helper(nums1,0, nums2,0, (len+1)/2);
43+
}
44+
45+
privateinthelper(int[]nums1,intm,int[]nums2,intn,intk) {
46+
if (m>= nums1.length)return nums2[n+ k-1];
47+
if (n>= nums2.length)return nums1[m+ k-1];
48+
if (k==1)returnMath.min(nums1[m], nums2[n]);
49+
50+
int p1= m+ k/2-1;
51+
int p2= n+ k/2-1;
52+
int mid1= p1< nums1.length? nums1[p1]:Integer.MAX_VALUE;
53+
int mid2= p2< nums2.length? nums2[p2]:Integer.MAX_VALUE;
54+
if (mid1< mid2) {
55+
return helper(nums1, m+ k/2, nums2, n, k- k/2);
56+
}
57+
return helper(nums1, m, nums2, n+ k/2, k- k/2);
58+
}
59+
}
60+
```
61+
62+
63+
##结语
64+
65+
如果你同我一样热爱数据结构、算法、LeetCode，可以关注我GitHub上的LeetCode题解：[awesome-java-leetcode][ajl]
66+
67+
68+
69+
[title]:https://leetcode.com/problems/median-of-two-sorted-arrays
70+
[ajl]:https://github.com/Blankj/awesome-java-leetcode

‎project/leetcode/.idea/workspace.xml

Lines changed: 484 additions & 181 deletions
Some generated files are not rendered by default. Learn more aboutcustomizing how changed files appear on GitHub.
Binary file not shown.
Binary file not shown.
Binary file not shown.

‎project/leetcode/src/com/blankj/easy/_021/Solution.java

Lines changed: 0 additions & 20 deletions
Original file line numberDiff line numberDiff line change
@@ -30,26 +30,6 @@ public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
3030

3131
publicstaticvoidmain(String[]args) {
3232
Solutionsolution =newSolution();
33-
ListNodelistNode00 =newListNode(1);
34-
ListNodelistNode01 =newListNode(3);
35-
ListNodelistNode02 =newListNode(5);
36-
ListNodelistNode03 =newListNode(7);
37-
ListNodelistNode04 =newListNode(9);
38-
listNode00.next =listNode01;
39-
listNode01.next =listNode02;
40-
listNode02.next =listNode03;
41-
listNode03.next =listNode04;
42-
listNode04.next =null;
43-
ListNodelistNode10 =newListNode(2);
44-
ListNodelistNode11 =newListNode(4);
45-
ListNodelistNode12 =newListNode(6);
46-
ListNodelistNode13 =newListNode(8);
47-
ListNodelistNode14 =newListNode(10);
48-
listNode10.next =listNode11;
49-
listNode11.next =listNode12;
50-
listNode12.next =listNode13;
51-
listNode13.next =listNode14;
52-
listNode14.next =null;
5333
ListNodelistNode0 =ListNode.createTestData("[1,3,5,7,9]");
5434
ListNodelistNode1 =ListNode.createTestData("[2,4,6,8,10]");
5535
ListNode.print(listNode0);
Lines changed: 46 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,46 @@
1+
packagecom.blankj.hard._004;
2+
3+
/**
4+
* <pre>
5+
* author: Blankj
6+
* blog : http://blankj.com
7+
* time : 2017/10/12
8+
* desc :
9+
* </pre>
10+
*/
11+
publicclassSolution {
12+
publicdoublefindMedianSortedArrays(int[]nums1,int[]nums2) {
13+
intlen =nums1.length +nums2.length;
14+
if (len %2 ==0) {
15+
return (helper(nums1,0,nums2,0,len /2) +helper(nums1,0,nums2,0,len /2 +1)) /2.0;
16+
}
17+
returnhelper(nums1,0,nums2,0, (len +1) /2);
18+
}
19+
20+
privateinthelper(int[]nums1,intm,int[]nums2,intn,intk) {
21+
if (m >=nums1.length)returnnums2[n +k -1];
22+
if (n >=nums2.length)returnnums1[m +k -1];
23+
if (k ==1)returnMath.min(nums1[m],nums2[n]);
24+
25+
intp1 =m +k /2 -1;
26+
intp2 =n +k /2 -1;
27+
intmid1 =p1 <nums1.length ?nums1[p1] :Integer.MAX_VALUE;
28+
intmid2 =p2 <nums2.length ?nums2[p2] :Integer.MAX_VALUE;
29+
if (mid1 <mid2) {
30+
returnhelper(nums1,m +k /2,nums2,n,k -k /2);
31+
}
32+
returnhelper(nums1,m,nums2,n +k /2,k -k /2);
33+
}
34+
35+
publicstaticvoidmain(String[]args) {
36+
Solutionsolution =newSolution();
37+
System.out.println(solution.findMedianSortedArrays(
38+
newint[]{1,3},
39+
newint[]{2}
40+
));
41+
System.out.println(solution.findMedianSortedArrays(
42+
newint[]{1,2},
43+
newint[]{3,4}
44+
));
45+
}
46+
}

0 commit comments

Comments
 (0)
[8]ページ先頭
©2009-2025 Movatter.jp