“The way you walk, just the way others walk

Read the title of classmate, believe to this problem have been very familiar with, is the fourth topic among leecode, was to write a separate writing mainly for me, it involves the knowledge is more important: dichotomy, but also provides a few simple exercises also encountered (behind), it is easier to understand. This question has also been asked by Apple, Microsoft, Amazon, Zenefits, Yahoo, Dropbox, and Adobe.

The title

Given two positively ordered (from small to large) arrays of size m and n nums1 and nums2. Find the median of the two Ordinal Numbers (that is, the number in the middle of an ordered set of data) and require the time complexity of the algorithm to be O(log(m + n)). You can assume that nums1 and nums2 are not empty at the same time.

Example 1: nums1 = [1, 3] Nums2 = [2] The median is 2.0

Example 2: nums1 = [1, 2] nums2 = [3, 4] Then the median is (2 + 3)/2 = 2.5

The time complexity is order log(m + n), so we want to use dichotomy to solve the problem. Here is a simple dichotomy:

For example, 123456789, if you want to find 2, first look for the middle element 5, which is greater than 2, so just exclude the 6789 to the right of 5, and then continue binary search in 1234. Every time you exclude 1/2, so it’s order log base n. A simple derivation:

derivation

There are n elements, and the interval size of each search is n, n over 2, n over 4… N over 2 to the k, where k is the number of loops. If n/2^k=1-> 2^k= n, then k=log base 2 of n, so the time complexity can be expressed as O()=O(logn).

To warm up, do some simple exercises

Exercise 1: Find a number

Basically, in an array, you give me a target number, and you find that number.

Reference code

int binarySearch(int[] nums, int target) {
int left = 0;
int right = nums.length - 1; / / note

  while(left <= right) {
      int mid = left + (right - left) / 2; / 1/3
      if(nums[mid] == target) // Whether it is in the middle
          return mid;
      else if (nums[mid] < target) // If the middle is removed, it must be on both sides. If the middle 
        left = mid + 1; / / note
      else if (nums[mid] > target)
        right = mid - 1; / / note
  }
  return -1;
}

 @Test
   public void isbinarySearch(a) {
   int[] nums = {1.2.2.2.3};
   int i = binarySearch(nums,4);
   Assert.assertNotNull(i);
 }
Copy the code

2. Dichotomy Exercise 2: Dichotomy search for the left edge **

Simply put, the target value is found, and if there are multiple target values, take the leftmost value.

Reference code

int left_bound(int[] nums, int target) {
    if (nums.length == 0) return -1;
    int left = 0;
    int right = nums.length; / / note

    while (left < right) { / / note
        int mid = left + (right - left) / 2; / 1/3
        if (nums[mid] == target) { // Look for the left and narrow the right
            right = mid;
        } else if (nums[mid] < target) {
            left = mid + 1;
        } else if (nums[mid] > target) {
            right = mid; / / note}}return left;
}

@Test
public void isleft_bound(a) {
    int[] nums = {1.2.2.2.3};
    int i = left_bound(nums, 2);
    Assert.assertNotNull(i);
}
Copy the code

Just a quick analysis, this is a little bit more difficult than the previous one

  1. Because to find the leftmost target value, the time complexity is logn, and the loop condition is left < right, if it is equal, it will exceed the time limit.
  2. Find the target value, now I can’t just return it, I need to find the leftmost target value, I can narrow the right, I can say right = mid, I can’t say right = mid -1, because this is the target = mid, if right is the leftmost target value then it might be a problem.

Back to the subject

These two exercises are very helpful for understanding this problem.

To find the median, you need to figure out the odd or even numbers of the total length, so if it’s odd, you take the median, and if it’s even, you take the middle two numbers over 2 as the median.

Ask two questions based on the example:

(1) Can we divide two arrays into one array

② If there are some cases that can not be divided into an array (such as an array with only one number but a large number), when the sum of two arrays is divided into two to 1, after the decimal number, take the minimum value of the two arrays as the median.

For the first question, example 1:

A: 1 2

B: 1 2 3 4 5 6 7 8 9 10

If the index of A is equal to the length1 of A, take the index of B +k(mid) -1.

If index1=length1, all values in array A are excluded as smaller values.

First of all we know that k=(length1+length2) + 1=7 this is the mid of the total length, we need the mid of each array and then we exclude the smaller ones, so k= k/2=3, we know that A is of length2, here if we take A value of length 3 we will cross the line, So let’s just take length1,

Select * from A where length1 = 1 and length1 = 2; select * from B where length1 = 3; select * from A where length1 = 2; select * from A where length1 = 1;

K = k-length-index1-1; k = k-k /2;

int index1 = 0, index2 = 0; // Initialize the index
if (index1 == length1) {
      return nums2[index2 + k - 1]; // The length of the array is calculated, so the index of the array is -1
}
Copy the code

Example 2:

A: 1 2 3 4 5 6 7 8 9 10

B: 1 2

Instead, I’m going to go straight to the conclusion here. We define the indexes of two arrays. If the index index2 of array B is equal to the length2 of array B, we take the index of array A +k(mid) -1.

 if (index2 == length2) {
     return nums1[index1 + k - 1];
 }
Copy the code

Example 3:

A: 100 200

B: 1 2 3 4 5 6 7 8 9

For an array like this, we can’t synthesize an array directly, but we can exclude the smaller values by constantly dicing, and when k is equal to 1, whoever is the smallest is the median.

Set the value of length1=200>3 and select k=k-k/2 =6-3=3 and index2=3. Select k=k-k/2 =6-3 and index2=3

K =k /2=1; k=k /2=1; k=k /2=1

Select * from array A where length=1; select * from array B where length=index2+half=5; select * from array A where length=1; select * from array B where length=index2+half=5; select * from array B where length=index2+half=5

When k=1, get A[1]=100,B[5]=6, because 100>6, so 6 is our median.

   if (k == 1) { 
      return Math.min(nums1[index1], nums2[index2]);
   }
Copy the code

Example 4:

A: 1 2 3 4 5 6 7 8 9

B: 1 2 3 4 5 6 7 8 9

This case can be analyzed according to case 3.

Reference code

public double findMedianSortedArrays(int[] nums1, int[] nums2) {
    int length1 = nums1.length, length2 = nums2.length;
    int totalLength = length1 + length2;
    if (totalLength % 2= =1) { / / odd
        int midIndex = totalLength / 2;
        double median = getKthElement(nums1, nums2, midIndex + 1);
        return median;
    } else {//
        int midIndex1 = totalLength / 2 - 1, midIndex2 = totalLength / 2;
        double median = (getKthElement(nums1, nums2, midIndex1 + 1) + getKthElement(nums1, nums2, midIndex2 + 1)) / 2.0;
        returnmedian; }}public int getKthElement(int[] nums1, int[] nums2, int k) {
    int length1 = nums1.length, length2 = nums2.length;
    int index1 = 0, index2 = 0; // Initialize the index
    int kthElement = 0;

    while (true) {
        // Boundary case
        if (index1 == length1) {
            return nums2[index2 + k - 1]; // The length of the array is calculated, so the index of the array is -1
        }
        if (index2 == length2) {
            return nums1[index1 + k - 1];
        }
        if (k == 1) {
            return Math.min(nums1[index1], nums2[index2]);
        }

        // Normal
        int half = k / 2;
        int newIndex1 = Math.min(index1 + half, length1) - 1;// k/2 - 1
        int newIndex2 = Math.min(index2 + half, length2) - 1;
        int pivot1 = nums1[newIndex1], pivot2 = nums2[newIndex2]; // Compare k/2-1
        if (pivot1 <= pivot2) {
            k -= (newIndex1 - index1 + 1); // k = k - k/2
            index1 = newIndex1 + 1;//
        } else {
            k -= (newIndex2 - index2 + 1); // k = k - k/2
            index2 = newIndex2 + 1; // Exclude impossible indexes}}}Copy the code

Test cases:

@Test
public void isfindMedianSortedArrays(a) {
    int[] nums1 = {1.2};
    int[] nums2 = {1.2.3.4.4.5.6.7.8.9.10}; // 
    double i = findMedianSortedArrays(nums1, nums2);
    Assert.assertNotNull(i);
}
Copy the code

summary

This question is mainly examined the use of dichotomy, do this question need to pay attention to all kinds of cases and the boundary of the treatment, this question can also be realized through the recursive way, the exit and the question consistent.

Popular recommendations:

  • Add the two numbers together

  • ThreadPoolExecutor thread pool

  • Add JVM parameters to microservices as they prepare to go live

  • [Leecode of the Day] The most important string with no duplicate characters

At the end of the article, I have compiled a recent interview data “Java Interview Customs Manual”, covering Java core technology, JVM, Java concurrency, SSM, microservices, database, data structure and so on. You can obtain it from GitHub github.com/Tingyu-Note… More to come.