/**
 * @Author :田宇寒.
 * @Date :Created in 14:19 2021年5月28日
 * @Description:leetcode4题 寻找两个正序数组中位数
 * @Modified By:
 * @Version: 1.0$
 */
public class code4 {

 public static void main(String[] args) {
 Solution2 solution = new Solution2();
 System.out.println(solution.findMedianSortedArrays(new int[]{1,3}, new int[]{2}));
 }

 static class Solution {
 public double findMedianSortedArrays(int[] nums1, int[] nums2) {
 /**
 * create by: 田宇寒
 * description: 将两个数组合并成一个大数组来计算 时间复杂度O(m+n) 空间复杂度O(m+n)
 * create time: 15:56 2021年5月28日
 * @Param: nums1
 * @Param: nums2
 * @return double
 */
 int totalLength = nums1.length + nums2.length;
 int[] allNums = new int[totalLength];
 int nums1Index = 0;
 int nums2Index = 0;
 for (int i = 0; i < totalLength ; i++) {
 if (nums1Index < nums1.length && nums2Index < nums2.length) {
 if (nums1[nums1Index] <= nums2[nums2Index]) {
 allNums[i] = nums1[nums1Index];
 if (nums1Index < nums1.length) {
 nums1Index++;
 }
 } else {
 allNums[i] = nums2[nums2Index];
 if (nums2Index < nums2.length) {
 nums2Index++;
 }
 }
 } else if (nums1Index >= nums1.length && nums2Index < nums2.length) {
 allNums[i] = nums2[nums2Index];
 nums2Index++;
 } else if (nums1Index < nums1.length && nums2Index >= nums2.length) {
 allNums[i] = nums1[nums1Index];
 nums1Index++;
 } else {
 return 0.0;
 }
 }
 if (totalLength % 2 == 0) {
 return (Double.valueOf(allNums[totalLength / 2 - 1]) + Double.valueOf(allNums[totalLength / 2])) /2;
 } else {
 return allNums[totalLength / 2];
 }
 }
 }

 static class Solution2 {
 public double findMedianSortedArrays(int[] nums1, int[] nums2) {
 /**
 * create by: 田宇寒
 * description: 找到中位数位置 移动指针法 时间复杂度O(m+n) 空间复杂度(1)
 * create time: 14:42 2021年5月31日
 * @Param: nums1
 * @Param: nums2
 * @return double
 */
 int m = nums1.length;
 int n = nums2.length;
 int len = m + n;
 int left = -1, right = -1;
 int aStart = 0, bStart = 0;
 for (int i = 0; i <= len / 2; i++) {
 left = right;
 if (aStart < m && (bStart >= n || nums1[aStart] < nums2[bStart])) {
 right = nums1[aStart++];
 } else {
 right = nums2[bStart++];
 }
 }
 if ((len & 1) == 0) {
 return (left + right) / 2.0;
 } else {
 return right;
 }
 }
 }
}