sirok

sirok
mail@pastecode.io avatar
unknown
java
2 years ago
7.0 kB
1
Indexable
Never
class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        
        int median1Index = (nums1.length - 1) / 2;
        System.out.println("median1Index:"+median1Index);
        int median2Index = (nums2.length - 1) / 2;
        int median1 = nums1[median1Index];
        System.out.println("median1:"+median1);
        int posOfMedian1InNums2 = binarySearch(nums2, median1);
        System.out.println("posOfMedian1InNums2:"+posOfMedian1InNums2);
        int numberOfElementsBeforeMedian1 = posOfMedian1InNums2;
        System.out.println("numberOfElementsBeforeMedian1:" + numberOfElementsBeforeMedian1);
        int numberOfElementsAfterMedian1 = nums2.length - numberOfElementsBeforeMedian1;
        System.out.println("numberOfElementsAfterMedian1:" + numberOfElementsAfterMedian1);
        int moveBy = numberOfElementsAfterMedian1 - numberOfElementsBeforeMedian1;
        System.out.println("mivaaan:" + nums1.length + ":" + nums2.length);
        if ((nums1.length + nums2.length) % 2 == 0){
            
            moveBy = moveBy - 1;
        }
        System.out.println("moveBy:" + moveBy);
        boolean medianIsInNums1 = true;
        boolean extraIsInNums1 = true;
        int nums2MoveBy = 0;
        int nums1MoveBy = 0;
        int extraIndex = 0;
        if (moveBy == 0){
            return median1;
        } else if (moveBy < 0){
            moveBy = moveBy * - 1;
            moveBy -=1;
            int k = posOfMedian1InNums2;
            while (moveBy > 0){
                if (nums2[k + nums2MoveBy - 1] > nums1[median1Index + nums1MoveBy - 1]){
                    nums2MoveBy--;
                    medianIsInNums1 = false;   
                } else {
                    nums1MoveBy--;
                    medianIsInNums1 = true;
                }
                moveBy--;
            }
            if (resultHasEvenNumberOfElements(nums1,nums2)){
                if (k + nums2MoveBy - 1 < 0 ){
                    extraIndex = nums1MoveBy-1;
                    extraIsInNums1 = true; 
                } else if (median1Index - 2 + nums1MoveBy < 0 ){
                    extraIndex = nums2MoveBy-1;
                    extraIsInNums1 = false;  
                }else if (nums2[k + nums2MoveBy - 1] < nums1[median1Index - 2 + nums1MoveBy]){
                    extraIndex = nums2MoveBy -1;
                    extraIsInNums1 = false;   
                } else {
                    extraIndex=nums1MoveBy-1;
                    medianIsInNums1 = true;
                }    
            }
        
        } else if (moveBy > 0){
            int k = posOfMedian1InNums2;
            while (moveBy > 0){
                if (nums2[k + nums2MoveBy] < nums1[median1Index + 1 + nums1MoveBy]){
                    nums2MoveBy++;
                    medianIsInNums1 = false;   
                } else {
                    nums1MoveBy++;
                    medianIsInNums1 = true;
                }
                moveBy--;
            }
            if (resultHasEvenNumberOfElements(nums1,nums2)){
                if (k + nums2MoveBy + 1 >= nums2.length ){
                    extraIndex = nums1MoveBy+1;
                    extraIsInNums1 = true;
                } else if (median1Index + 2 + nums1MoveBy >= nums1.length){
                    extraIndex = nums2MoveBy+1;
                    extraIsInNums1=false;
                } else if (nums2[k + nums2MoveBy + 1] < nums1[median1Index + 2 + nums1MoveBy]){
                    extraIndex = nums2MoveBy +1;
                    extraIsInNums1 = false;   
                } else {
                    extraIndex=nums1MoveBy+1;
                    medianIsInNums1 = true;
                }    
            }
        }
        if (resultHasEvenNumberOfElements(nums1,nums2)){
            System.out.println(extraIsInNums1 + " " + nums1[median1Index + nums1MoveBy]);
            System.out.println(medianIsInNums1 + " " + nums2[posOfMedian1InNums2 + extraIndex - 1]);
            if (medianIsInNums1 && extraIsInNums1){
                return ((double)nums1[median1Index + nums1MoveBy] + (double)nums1[median1Index + extraIndex]) / 2;
            } else if (medianIsInNums1 && !extraIsInNums1){
                return ((double)nums1[median1Index + nums1MoveBy] + (double)nums2[posOfMedian1InNums2 + extraIndex - 1]) / 2;    
            } else if (!medianIsInNums1 && extraIsInNums1){
                return ((double)nums2[posOfMedian1InNums2 + nums2MoveBy - 1] + (double)nums1[median1Index + extraIndex]) / 2;   
            } else if (!medianIsInNums1 && ! extraIsInNums1){
                return ((double)nums2[posOfMedian1InNums2 + nums2MoveBy - 1] + (double)nums2[posOfMedian1InNums2 + extraIndex - 1]) / 2;       
            }
        }
        if (medianIsInNums1){
            return nums1[median1Index + nums1MoveBy];
        } else {
            return nums2[posOfMedian1InNums2 + nums2MoveBy - 1];
        }
    }
    
    public int binarySearch(int[] nums, int target){
        int lowIndex = 0;
        int highIndex = nums.length - 1;
        while (lowIndex < highIndex){
            int mid = (lowIndex + highIndex) / 2;
            if (nums[mid] == target){
                return mid;
            } else if (lowIndex+1 == highIndex && nums[lowIndex] != target && nums[highIndex] != target) { 
                if (target < nums[lowIndex]){
                    return lowIndex;
                } else if (target > nums[highIndex]){
                    return highIndex + 1;
                } else {
                    return highIndex;
                }
            }else if (target > nums[mid]){
                lowIndex = mid + 1;
            } else if (target < nums[mid]){
                highIndex = mid - 1;
            }
        }
        return highIndex;
    }
    
    public boolean resultHasEvenNumberOfElements(int[] nums1, int[] nums2){
        return (nums1.length + nums2.length) % 2 == 0;
    }
    
    public double handleTrivialCases (int[] nums1, int[] nums2){
        if (nums1.length == 0 && nums2.length == 1){
            return nums2[0];
        }
        if (nums1.length == 1 && nums2.length == 0){
            return nums1[0];
        }
        if (nums1.length == 0){
            if (nums2.length % 2 == 0){
                int index1 = (nums2.length -1) /2;
                int index2 = index1+1;
                return ((double)nums2[index1] + (double)nums2[index2])/2;
            } else {
                return nums2[(nums2.length - 1) / 2];
            }
        }
        if (nums2.length == 0){
             if (nums1.length % 2 == 0){
                int index1 = (nums1.length -1) /2;
                int index2 = index1+1;
                return ((double)nums1[index1] + (double)nums1[index2])/2;
            } else {
                return nums1[(nums1.length - 1) / 2];
            }    
        }
    }
}