β π‘ Personal homepage: Program ape chase

β π‘ Series column: Algorithm set

β π‘ Current status: create Java learning road (zero foundation to employment practice) series, which is currently updated to JAVAWEB development

β π‘ About the author: Hello, everyone. I'm a program ape chaser, a new star creator in the whole stack field, and an algorithm enthusiast. I often rank in the top 30 of the weekly list of authors. I'm an unknown ACMer

β π‘ Recommend a website that can't fail in question brushing, interview and job hunting—— Niuke.com

β π‘ Personal famous saying: take advantage of youth, work hard, and give an account to yourself in the future!

Hello, everyone, I'm program ape chase. Through the last private letter in French, a little friend left a message saying, when will it be updated? see? It will come today.

catalogue

Search in two-dimensional array

# Binary search-I

describe

Please realize binary search of ascending array without repeated numbers

Given an integer array nums with ascending elements and no repeated numbers and a target value target, write a function to search the target in nums. If the target value exists, return the subscript (the subscript starts from 0), otherwise return -1

Data range: 0 ≤ len (Num) ≤ 2 × 105, any value in the array meets β£ val β£ ≤ 109

Advanced: time complexity O(logn), space complexity O(1)

Example 1

Input:

[-1,0,3,4,6,10,13,14],13

Return value:

6

explain:

13 appears in nums with subscript 6

Example 2

Input:

[],3

Return value:

-1

explain:

Num is empty, return -1

Example 3

Input:

[-1,0,3,4,6,10,13,14],2

Return value:

-1

explain:

2 does not exist in nums, so -1 is returned

## Problem solving code

import java.util.*; public class Solution { public int search (int[] nums, int target) { int l = 0; int r = nums.length - 1; //Start from the beginning and end of the array until they meet fast template while(l <= r){ //The value of the midpoint of each check int m = (l + r) / 2; if(nums[m] == target) return m; //Enter the left section if(nums[m] > target) r = m - 1; //Enter the right section else l = m + 1; } //not found return -1;} }

# Search in two-dimensional array

describe

In a two-dimensional array (each one-dimensional array has the same length), each row is sorted in ascending order from left to right, and each column is sorted in ascending order from top to bottom. Please complete a function, input such a two-dimensional array and an integer, and judge whether the array contains the integer.

[

[1,2,8,9],

[2,4,9,12],

[4,7,10,13],

[6,8,11,15]

]

Given target = 7, return true.

Given target = 3, return false.

Data range: the length and width of the matrix meet 0 ≤ n,m ≤ 500, and the values in the matrix meet 0 ≤ val ≤ 109

Advanced: space complexity O(1), time complexity O(n+m)

Example 1

Input:

7,[[1,2,8,9],[2,4,9,12],[4,7,10,13],[6,8,11,15]]

Copy return value:

true

explain:

Exist 7, return true

Example 2

Input:

1,[[2]]

Return value:

false

Example 3

Input:

3,[[1,2,8,9],[2,4,9,12],[4,7,10,13],[6,8,11,15]]

Return value:

false

explain:

If 3 does not exist, false is returned

## Problem solving code

public class Solution { public boolean Find(int target, int [][] array) { //Give priority to special fast template if(array.length == 0) return false; int n = array.length; if(array[0].length == 0) return false; int m = array[0].length; //Start from the element in the bottom left corner to the left or up for(int i = n - 1, j = 0; i >= 0 && j < m; ){ //The element is large, go up if(array[i][j] > target) i--; //The element is small, go to the right else if(array[i][j] < target) j++; else return true; } return false;} }

# Looking for peak

describe

Given an array num of length n, please find the peak value and return its index. The array may contain multiple peaks. In this case, just return any location.

1. Peak element refers to the element whose value is strictly greater than the left and right adjacent values. Strictly greater than, that is, there cannot be equal to

2. Assume nums[-1] = nums[n] = − ∞

3. There are nums[i] for all valid I= nums[i + 1]

4. Can you use the time complexity of O(logN) to solve this problem?

Data range:

1β€nums.lengthβ€2Γ10^5Β

-2^31<=nums[i]<=2^31 β 1

If you enter [2,4,1,2,7,8,4], two peaks will be formed, one with index 1 and peak value 4, and the other with index 5 and peak value 8, as shown in the following figure:

Β

Example 1

Input:

[2,4,1,2,7,8,4]

Return value:

1

explain:

Both 4 and 8 are peak elements. Index 1 of 4 or index 5 of 8 can be returned

Example 2

Input:

[1,2,3,1]

Return value:

2

explain:

3 is the peak element, and its index 2 is returned

## Problem solving code

import java.util.*; public class Solution { public int findPeakElement (int[] nums) { int left = 0; int right = nums.length - 1; //Dichotomy fast template while(left < right){ int mid = (left + right) / 2; //The right side is down, and there may not be a slope peak if(nums[mid] > nums[mid + 1]) right = mid; //On the right, it's going up. You must find the crest else left = mid + 1; } //One of the peaks return right;} }

# Reverse pairs in an array

describe

Two numbers in the array. If the previous number is greater than the following number, the two numbers form an inverse pair. Enter an array and find the total number of reverse pairs P in this array. And output the result of P's modulus of 1000000007. That is, output P mod 1000000007

Data range: for 50% of data, size ≤ 10^6

For 100% data, size ≤ 105

The values of all numbers in the array meet 0 ≤ val ≤ 1000000

Β

Requirements: space complexity O(n), time complexity O(nlogn)

Enter Description:

The title ensures that the same number does not exist in the input array

Example 1

Input:

[1,2,3,4,5,6,7,0]

Return value:

7

Example 2

Input:

[1,2,3]

Return value:

0

## Problem solving code

public class Solution { public int mod = 1000000007; public int mergeSort(int left, int right, int [] data, int [] temp){ // Stop dividing fast template if (left >= right) return 0; //Take the middle int mid = (left + right) / 2; //Left right division int res = mergeSort(left, mid, data, temp) + mergeSort(mid + 1, right, data, temp); //Prevent overflow res %= mod; int i = left, j = mid + 1; for (int k = left; k <= right; k++) temp[k] = data[k]; for (int k = left; k <= right; k++) { if (i == mid + 1) data[k] = temp[j++]; else if (j == right + 1 || temp[i] <= temp[j]) data[k] = temp[i++]; //The left is larger than the right, and the answer increases else { data[k] = temp[j++]; // Statistical reverse order pair res += mid - i + 1; } } return res % mod; } public int InversePairs(int [] array) { int n = array.length; int[] res = new int[n]; return mergeSort(0, n - 1, array, res);} }

Algorithms are extremely important to programmers. The language and development platform are constantly changing, but those algorithms and theories remain unchanged. I vaguely remember my senior who played well (he got an offer in his sophomore year). He told me that if I want to find a good job, it must be essential to brush questions

At present, there are quite a lot of algorithm question brushing platforms. I would like to introduce a platform that I think is most closely related to big companies—— Niuke.com