In algorithm interviews, interviewers always like to make articles around linked lists, sorting, binary trees, and binary search, and most people can follow professional books to memorize them. The interviewer does not want to recruit a programmer with good memory skills but cannot learn and apply it. Therefore, it is very important to learn to model and analyze problems mathematically and use reasonable algorithms or data structures to solve problems.
Interview question: Print out the minimum number of the rotating array
Title: Move the first several elements of an array to the end of the array, which we call the rotation of the array. Enter a rotation of an incrementally sorted array and output the minimum element of the rotation array. For example, array {3, 4, 5, 1, 2} is a rotation of array {1, 2, 3, 4, 5}, and the minimum value of the array is 1.
To achieve this requirement, we just need to traverse the array, find the smallest value and exit the loop directly. The code implementation is as follows:
public class Test08 { public static int getTheMin(int nums[]) { if (nums == null || nums.length == 0) { throw new RuntimeException("input error!"); } int result = nums[0]; for (int i = 0; i < nums.length - 1; i++) { if (nums[i + 1] < nums[i]) { result = nums[i + 1]; break; } } return result; } public static void main(String[] args) { // Typical input, a rotation of a monotonic ascending array int[] array1 = {3, 4, 5, 1, 2}; System.out.println(getTheMin(array1)); // There are duplicate numbers, and the smallest number that is just the smallest number int[] array2 = {3, 4, 5, 1, 1, 2}; System.out.println(getTheMin(array2)); // There are duplicate numbers, but the duplicate numbers are not the first and last numbers int[] array3 = {3, 4, 5, 1, 2, 2}; System.out.println(getTheMin(array3)); // There are duplicate numbers, and the duplicate numbers happen to be the first and last numbers int[] array4 = {1, 0, 1, 1, 1}; System.out.println(getTheMin(array4)); // Monotone ascending array, rotate 0 elements, that is, the monotonic ascending array itself int[] array5 = {1, 2, 3, 4, 5}; System.out.println(getTheMin(array5)); // There is only one number in the array int[] array6 = {2}; System.out.println(getTheMin(array6)); // The numbers in the array are the same int[] array7 = {1, 1, 1, 1, 1, 1, 1}; System.out.println(getTheMin(array7)); }}There is nothing wrong with printing results. However, this method is obviously not the best. Let's see if there is a way to find a better method to deal with it.
Orderly, still need to search?
When we find these two keywords, we will inevitably think of our binary search method, but many friends will definitely ask that our array is no longer a truly ordered array after being rotated, but it is like a combination of two incremental arrays. We can think like this.
We can set two subscripts low and high, and set mid = (low + high)/2, and we can naturally find the element array[mid] in the middle of the array. If the middle element is in the incremental array in front, then it should be greater than or equal to the corresponding element of the low subscript. At this time, the smallest element in the array should be behind the element. We can point the low subscript to the intermediate element, which can narrow the range of searches.
Similarly, if the intermediate element is located in the subsequent incremental subarray, it should be less than or equal to the element corresponding to the high subscript. At this time the smallest element in the array should be in front of the intermediate element. We can update the high subscript to the median subscript, which can also narrow the range of searches. The elements corresponding to the high subscript after moving are still in the subsequent incremental subarray.
Whether it is updating low or high, our search range will be reduced to half of the original. Next, we will use the updated subscript to repeat a new round of searches. Until the last two subscripts are adjacent, that is, our loop end condition.
I have said a lot, and it seems that I have been in a mess. We might as well use the input in the question to simulate and verify our algorithm.
Let’s take a look at how to implement this idea in Java using code:
public class Test08 { public static int getTheMin(int nums[]) { if (nums == null || nums.length == 0) { throw new RuntimeException("input error!"); } // If there is only one element, directly return if (nums.length == 1) return nums[0]; int result = nums[0]; int low = 0, high = nums.length - 1; int mid; // Make sure that the value corresponding to the low subscript is in the increment subarray on the left, and the value corresponding to the high is in the increment subarray on the right while (nums[low] >= nums[high]) { // Ensure the end of the loop condition if (high - low == 1) { return nums[high]; } // Take the middle position mid = (low + high) / 2; // Indicates that the middle element is incremented on the left if (nums[mid] >= nums[low]) { low = mid; } else { high = mid; } } return result; } public static void main(String[] args) { // Typical input, a rotation of a monotonic ascending array int[] array1 = {3, 4, 5, 1, 2}; System.out.println(getTheMin(array1)); // There are duplicate numbers and the smallest number that just repeats the numbers is int[] array2 = {3, 4, 5, 1, 1, 2}; System.out.println(getTheMin(array2)); // There are duplicate numbers, but the duplicate numbers are not the first and last numbers int[] array3 = {3, 4, 5, 1, 2, 2}; System.out.println(getTheMin(array3)); // There are duplicate numbers, and the duplicate numbers are exactly the first and last numbers int[] array4 = {1, 0, 1, 1, 1}; System.out.println(getTheMin(array4)); // Monotonous ascending array, rotate 0 elements, that is, the monotonous ascending array itself int[] array5 = {1, 2, 3, 4, 5}; System.out.println(getTheMin(array5)); // There is only one number in the array int[] array6 = {2}; System.out.println(getTheMin(array6)); // The numbers in the array are the same int[] array7 = {1, 1, 1, 1, 1, 1, 1, 1}; System.out.println(getTheMin(array7)); // Special I don't know how to move int[] array8 = {1, 0, 1, 1, 1}; System.out.println(getTheMin(array8)); }}We mentioned earlier that in a rotating array, since several numbers in the incrementally sorted array are moved behind the array, the first number is always greater than or equal to the last number, and there is another special case that 0 elements are moved, that is, the array itself is also its own rotating array. This situation itself is ordered, so we just need to return the first element, which is why I assign the result to nums[0] first.
Is the above code perfect? We did not meet our requirements through the test cases. Let’s take a look at the array8 input in detail. Let’s first analyze the computer operation:
But we can see at a glance that our minimum value is not 1, but 0, so when array[low], array[mid], and array[high] are equal, our program does not know how to move. According to the current movement method, the array[mid] is incremented on the left by default. This is obviously irresponsible.
Let's correct the code:
public class Test08 { public static int getTheMin(int nums[]) { if (nums == null || nums.length == 0) { throw new RuntimeException("input error!"); } // If there is only one element, directly return if (nums.length == 1) return nums[0]; int result = nums[0]; int low = 0, high = nums.length - 1; int mid = low; // Make sure that the value corresponding to the low subscript is in the increment subarray on the left, and the value corresponding to the high is in the increment subarray on the right while (nums[low] >= nums[high]) { // Ensure the end of the loop condition if (high - low == 1) { return nums[high]; } // Take the middle position mid = (low + high) / 2; // In special cases where the three values are equal, you need to find the smallest value from beginning to end if (nums[mid] == nums[low] && nums[mid] == nums[high]) { return midInorder(nums, low, high); } // Indicates that the middle element is incremented on the left if (nums[mid] >= nums[low]) { low = mid; } else { high = mid; } } return result; } /** * Find the minimum value in the array* * @param nums array* @param start Array start position* @param end Array end position* @return The smallest number found*/ public static int midInorder(int[] nums, int start, int end) { int result = nums[start]; for (int i = start + 1; i <= end; i++) { if (result > nums[i]) result = nums[i]; } return result; } public static void main(String[] args) { // Typical input, a rotation of a monotonic ascending array int[] array1 = {3, 4, 5, 1, 2}; System.out.println(getTheMin(array1)); // There are duplicate numbers and the smallest number that just happens to be the most common number int[] array2 = {3, 4, 5, 1, 1, 2}; System.out.println(getTheMin(array2)); // There are duplicate numbers, but the duplicate numbers are not the first and last numbers int[] array3 = {3, 4, 5, 1, 2, 2}; System.out.println(getTheMin(array3)); // There are duplicate numbers, and the duplicate numbers are exactly the first and last numbers int[] array4 = {1, 0, 1, 1, 1}; System.out.println(getTheMin(array4)); // Monotonous ascending array, rotate 0 elements, that is, the monotonous ascending array itself int[] array5 = {1, 2, 3, 4, 5}; System.out.println(getTheMin(array5)); // There is only one number in the array int[] array6 = {2}; System.out.println(getTheMin(array6)); // All numbers in the array are the same int[] array7 = {1, 1, 1, 1, 1, 1, 1}; System.out.println(getTheMin(array7)); // Special I don't know how to move int[] array8 = {1, 0, 1, 1, 1}; System.out.println(getTheMin(array8)); }}We then put it in with complete test cases and the test passes.
Summarize
In fact, this question has many points to examine, but in fact it is to examine the flexible application of binary search. Many friends must follow orderly memorize binary searches without learning the idea of binary search, which will lead to only thinking about circular search minimum values.
Many friends made a statement during the interview that the Android original ecosystem basically encapsulated common algorithms and protested against these ineffective algorithms in the interview. This is actually quite stupid. We do not seek to implement rote algorithms, but we seek to learn the clever ideas in it. Only by constantly improving one's thinking ability can one help one gain better career development.
The above is all the content of this article. I hope it will be helpful to everyone's learning and I hope everyone will support Wulin.com more.