This is the 11th day of my participation in Gwen Challenge

Find the smallest letter larger than the target letter (744)

Topic describes

You are given a sorted list of letters, containing only lowercase Letters. Given another target letter, look for the smallest letter in the sequence list that is larger than the target letter.

In comparison, the letters appear in a circular order. Here’s an example:

  • If the target lettertarget = 'z'And the character list isletters = ['a', 'b'], the answer is returned'a'

Example 1:

Input: letters = [" c ", "f", "j]" target = "a" output: "c" type: letters = [" c ", "f", "j]" target = "c" output: "f" type: Letters = [" c ", "f", "j]" target = "d" output: "f" input: letters = [" c ", "f", "j]" target = "g" output: "j" type: Letters = [" c ", "f", "j]" target = "j" output: "c" type: letters = [" c ", "f" and "j"] target = "k" output: "c"Copy the code

prompt

  • lettersLength range within[2, 10000]Range.
  • lettersContains only lowercase letters and at least two different letters.
  • Target letterstargetIt’s a lowercase letter.

Thought analysis

Look for the smallest letter that is larger than the target letter. The target letter may not be in the sorted character list, so if the target letter is smaller than the first letter of the sorted letter, it is returned. We use binary lookup because the character list is already sorted. If the target letter is equal to one of these letters, then we keep finding the smallest letter greater than that letter.

Binary search has certain routines, first define low and high. The judgment condition of the while loop is always low <= high. For low == high, special processing is made when necessary, and the return value is always mid. Low = mid + 1 and high = mid – 1;

For the non-deterministic search, the pre – and post-detection method is used to determine the search interval. We deal with hits first, and then we deal with left and right half look-ups.

The code shown

Solution 1: Time complexity is O(logn){O(logn)}O(logn), space complexity is O(1){O(1)}O(1).

public char nextGreatestLetter(char[] letters, char target) { // a b c d c
        int low = 0;
        int high = letters.length - 1;
        while (low <= high){
            int mid = low + (high - low)/2;
            if ((mid == 0 || letters[mid - 1] <= target) && letters[mid] > target){
                return letters[mid];
            } else if (target > letters[mid]){
                low = mid + 1;
            } else if (target < letters[mid]){
                high = mid - 1;
            } else if(letters[mid] == target){
                low = mid + 1; }}return letters[0];
    }
Copy the code

Searching a two-dimensional matrix (74)

Topic describes

Write an efficient algorithm to determine whether there is a target value in an M x n matrix. The matrix has the following characteristics:

  • The integers in each row are arranged in ascending order from left to right.
  • The first integer in each line is greater than the last integer in the previous line.

Advanced:

  • You can be inO(n log n)Sorting linked lists in time complexity and constant space complexity?

Example 1:

Input: matrix = [hc-positie [1], [10,11,16,20], [23,30,34,60]], target = 3 output: trueCopy the code

Example 2:

Input: matrix = [hc-positie [1], [10,11,16,20], [23,30,34,60]], target = 13 output: falseCopy the code

prompt

  • m == matrix.length
  • n == matrix[i].length
  • 1 <= m, n <= 100
  • -104 <= matrix[i][j], target <= 104

Thought analysis

This problem also uses binary search, and the difficulty is that we need to deal with binary search for a two-dimensional matrix, where the index of the row is mid/n and the index of the column is mid%n; The subsequent processing is no different from normal binary search.

The code shown

Solution 1: Time complexity is O(n){O(n)}O(n), space complexity is O(1){O(1)}O(1).

		/ / [[1, 3, 5, 7)
    / /,11,16,20 [10]
    / / [23,30,34,60]], 5
    public boolean searchMatrix(int[][] matrix, int target) {
        int m = matrix.length; / / 3
        int n = matrix[0].length; / / 4

        int low = 0;
        int high = m * n - 1;
        while (low <= high){
            int mid = low + (high - low)/2;  / / 5
            int i = mid / n;  / / line
            int j = mid % n;       / / column
            int value = matrix[i][j];
            if (target == value){
                return true;
            } else if (target > value){
                low = mid + 1;
            } else {
                high = mid - 1; }}return false;
    }
Copy the code

conclusion

For sorted problems, binary search can greatly reduce the time complexity, we should be familiar with binary and its related variations.

Binary search has certain routines, first define low and high. The judgment condition of the while loop is always low <= high. For low == high, special processing is made when necessary, and the return value is always mid. Low = mid + 1 and high = mid – 1;

For the non-deterministic search, the pre – and post-detection method is used to determine the search interval. We deal with hits first, and then we deal with left and right half look-ups.