要求:任意两个数组取中位数,在保证空间复杂度的同时,时间复杂度要求log(m + n)
package com.flash.hance;
import java.util.ArrayList;
import java.util.List;
/**
* @author: lizheng
*/
public class Test {
/**
* 查找中位数
* @param nums1
* @param nums2
* @return
*/
public Double findMedianSortedArrays(int[] nums1, int[] nums2) {
Middle middle = new Middle(0, nums1.length + nums2.length);
String string = "";
string.toCharArray();
// 1.空数组判断
if (nums1.length == 0) {
return (nums2[middle.getFirstFlag()] + nums2[middle.getSecondFlag()]) / 2D;
}
if (nums2.length == 0) {
return (nums1[middle.getFirstFlag()] + nums1[middle.getSecondFlag()]) / 2D;
}
NumsData numsData1 = new NumsData(nums1);
NumsData numsData2 = new NumsData(nums2);
// 具体的查找动作
return doFindMedian(numsData1, numsData2, middle);
}
/**
*
* @param nums1
* @param nums2
* @param middle
* @return
*/
public Double doFindMedian(NumsData nums1, NumsData nums2, Middle middle) {
int length = nums1.getLength() + nums2.getLength();
// 1.小数组采用排序法处理
if (length <= 4) {
// 数组排序并打印
return culBySort(nums1, nums2, middle);
}
// 2.获取两个数组的中位数
Middle middle4Nums1 = new Middle(0, nums1.getLength());
Integer nums1SecondData = nums1.getByIndex(middle4Nums1.getSecondFlag());
Middle middle4Nums2 = new Middle(0, nums2.getLength());
Integer nums2SecondData = nums2.getByIndex(middle4Nums2.getSecondFlag());
if (nums1SecondData >= nums2SecondData) {
// 取第一个数组的后半部分;第二数组的前半部分
nums1.setRightOffset(middle4Nums1.getSecondFlag());
nums2.setLeftOffset(middle4Nums2.getSecondFlag());
} else {
// 取第一数组的前半部分;第二个数组的后半部分
nums1.setLeftOffset(middle4Nums1.getSecondFlag());
nums2.setRightOffset(middle4Nums2.getSecondFlag());
}
return doFindMedian(nums1, nums2, middle);
}
/**
* 通过数组排序的方法计算中值
* @param nums1
* @param nums2
* @return
*/
public Double culBySort(NumsData nums1, NumsData nums2, Middle middle) {
List<Integer> list = new ArrayList<Integer>();
Integer nu2Flag = 0;
// 数组排序
for (int i = 0; i < nums1.getLength(); i++) {
for (int j = nu2Flag; j < nums2.getLength(); j++) {
if (nums1.getByIndex(i) < nums2.getByIndex(j)) {
list.add(nums1.getByIndex(i));
break;
} else if (nums1.getByIndex(i) == nums2.getByIndex(j)) {
list.add(nums1.getByIndex(i));
list.add(nums2.getByIndex(j));
nu2Flag = nu2Flag < j + 1 ? j + 1 : nu2Flag;
break;
} else {
nu2Flag = nu2Flag < j + 1 ? j + 1 : nu2Flag;
list.add(nums2.getByIndex(j));
}
}
}
if (nu2Flag < nums2.getLength()) {
for (int i = nu2Flag; i < nums2.getLength(); i++) {
list.add(nums2.getByIndex(i));
}
}
// 取中值
int leftOffset = nums1.getLeftOffset() + nums2.getLeftOffset();
return (list.get(middle.getFirstFlag() - leftOffset) + list.get(middle.getSecondFlag() - leftOffset)) / 2D;
}
public static void main(String[] args) {
Test test = new Test();
// int[] nums1 = {0, 1,2};
// int[] nums2 = {};
// int[] nums1 = {0, 1,2};
// int[] nums2 = {3, 4, 5};
// int[] nums1 = {0, 1,2};
// int[] nums2 = {3};
// int[] nums1 = {0, 1,3};
// int[] nums2 = {2};
// int[] nums1 = {0, 1, 2, 7, 8};
// int[] nums2 = {3,4,5,6};
int[] nums1 = {1, 2};
int[] nums2 = {-1, 3};
double result = test.findMedianSortedArrays(nums1, nums2);
System.out.println(result);
}
}
/**
* 数据包装对象:
* 提供getLength、getIndex方法,对外屏蔽掉偏移量
*/
class NumsData {
int[] data;
int leftOffset;
int rightOffset;
public NumsData(int[] data) {
this.data = data;
this.leftOffset = 0;
this.rightOffset = 0;
}
public NumsData(int[] data, int leftOffset, int rightOffset) {
this.data = data;
this.leftOffset = leftOffset;
this.rightOffset = rightOffset;
}
public int[] getData() {
return data;
}
public void setData(int[] data) {
this.data = data;
}
public int getLeftOffset() {
return leftOffset;
}
public void setLeftOffset(int leftOffset) {
this.leftOffset += leftOffset;
}
public int getRightOffset() {
return rightOffset;
}
public void setRightOffset(int rightOffset) {
this.rightOffset += rightOffset;
}
public Integer getLength() {
return data.length - leftOffset - rightOffset;
}
public Integer getByIndex(Integer index) {
return data[index + leftOffset];
}
}
/**
* 中位数坐标
*/
class Middle {
private Integer firstFlag; // 中位数所处坐标,从0开始
private Integer secondFlag; // 中位数所处坐标,从0开始
public Middle(Integer length1, Integer length2) {
int length = length1 + length2;
int mod = length % 2;
if (mod == 0) {
secondFlag = length >> 1;
firstFlag = secondFlag - 1;
} else {
firstFlag = secondFlag = length >> 1;
}
}
public Integer getFirstFlag() {
return firstFlag;
}
public void setFirstFlag(Integer firstFlag) {
this.firstFlag = firstFlag;
}
public Integer getSecondFlag() {
return secondFlag;
}
public void setSecondFlag(Integer secondFlag) {
this.secondFlag = secondFlag;
}
}