Preface explains

Algorithm learning, daily brush record.

Subject to connect

The weakest fighting row in the matrix is K

The subject content

You are given a matrix mat of size m by n, consisting of a number of soldiers and civilians, represented by ones and zeros.

Return the index of the weakest row k in the matrix, sorted from weakest to strongest.

If line I has fewer soldiers than line J, or if both lines have the same number of soldiers but I is less than J, then line I is considered weaker than line J.

Soldiers are always at the top of the line, which means that the 1 always comes before the 0.

Example 1:

Enter: mat =

k = 3

Output:,0,3 [2]

Explanation:

Number of soldiers in each line:

0 – > 2

1 – > 4 lines

Line 2 – > 1

Line 3 – > 2

Line 4 – > 5

Sorting these rows from weakest to strongest gives [2,0,3,1,4]

Example 2:

Enter: mat =

k = 2

Output: [0, 2]

Explanation:

Number of soldiers in each line:

0 – > 1

1 – > 4 lines

Line 2 – > 1

Line 3 – > 1

Sort these rows from weakest to strongest to get [0,2,3,1]

Tip:

m == mat.length

n == mat[i].length

2 <= n, m <= 100

1 <= k <= m

Matrix [I][j] is either 0 or 1

The analysis process

There are altogether 3 methods, from method 1 to method 3, step by step optimization.

Method 2 is optimized on the basis of method 1.

Method 3 is optimized on the basis of method 2.

Method 1

Count the number of soldiers in each row, use the modified bubble sort to sort, take the first K after sorting.

Note: here is sorted according to the number of soldiers in a row to sort, but turned out to be the corresponding line of the standard can be removed, rather than the number of soldiers in a row, so this list to save the number of soldiers, each row lists the elements using an array, the array with two elements save the number of soldiers in a row and line standard respectively.

The first step

The first element of int[] holds the line identifier, and the second element holds the number of soldiers in the line.

The second step

Traversing the rows of the matrix MAT:

Obtain the row row of matrix MAT.

2, define the number of soldiers count, starting with 0.

3, Iterate over each row column as follows:

If the element is 1, it’s the soldier, and the number of soldiers count plus 1.

4, save the number of soldiers in each row to list, as an array, the first element of the array holds the number of soldiers in the line I, the second element holds the number of soldiers in the line count.

The third step

Select * from list (int[], int[], int[], int[], int[], int[]);

1, The number of rows that need to be sorted is exactly equal to the length of the list minus 1. For each row, find the current maximum number and move to the corresponding position.

2. In the first layer for loop, add isFlag to check whether the list list is in order. The initial value is true, and then carry out the second layer for loop.

3. In the second layer of the for loop, each time you sort, compare the size of the current element with the size of the next element, and move the larger element back.

Since the list element is int[], the second element of the array holds the number of soldiers, so the comparison element is the second element of the array.

If the current number of soldiers is greater than the next number, swap the elements of their corresponding list list.

The list list is not yet in order because of swapping. Set isFlag to false.

If isFlag is true, then the list is in order. If isFlag is true, then the list is in order. Otherwise, the first for loop continues until the end.

The fourth step

Define the result array nums to hold the number of soldiers in the first k rows after sorting.

Loop from 0 to k-1, construct result array nums, loop:

Assign the row label of the sorted list directly to the result array nums.

Step 5

Returns the result array nums.

To solve the code
Class Solution {public int[] kWeakestRows(int[][] mat, int k) { Int [], int[], int[], int[], int[] List<int[]> List = new ArrayList<>(); For (int I = 0; i < mat.length; Int [] row = mat[I]; Int count = 0; For (int col: row) {if (1 == col) {// If (1 == col) { List.add (new int[]{I, count}); list.add(new int[]{I, count}); } // Select * from a list (O(n^2), O(n^2), O(n^2), O(n^2), O(n^2), O(n^2); Int I = 0; int I = 0; int I = 0; i < list.size() - 1; ++ I) {// Check whether the list is in order Boolean isFlag = true; For (int j = 0; for (int j = 0; for (int j = 0; j < list.size() - 1 - i; Int before = list.get(j)[1]; ++j) {int before = list.get(j)[1]; Int next = list.get(j + 1)[1]; int next = list.get(j + 1)[1]; Int [] temp = list.get(j); if (before > next) {// If (before > next) {int[] temp = list.get(j); list.set(j, list.get(j + 1)); list.set(j + 1, temp); // The list is not ordered isFlag = false; }} if (isFlag) {// If the list is in order, break the loop; Int [] nums = new int[k]; Nums for (int I = 0; i < k; ++ I) {nums nums[I] = list.get(I)[0]; } return nums; }}Copy the code
Submit the results

It took 5ms to execute, beating 6.90% of users in time, 39.3MB in memory consumption, and 79.76% in space.

Method 2

The execution time of method 1 is too poor, so method 2 is optimized on top of method 1.

Method 2 instead of using array RES to store the number and label of soldiers in each row, use one number to store two pieces of information.

Array. Sort is more efficient than bubble-sort method 1, and mod the elements of the sorted array res to 100. You can get the row label sorted by the number of soldiers.

Why times 100?

Because they specify that the length of the matrix is 100, so the maximum number of soldiers is 100, and the maximum number of rows is 99, and when you multiply the number of soldiers by 100, the relative size is still the same, and then you add the row, because the maximum row is 99, less than 100, it doesn’t change the relative size because of the row, The size of the travel object can be compared on the basis of the number of soldiers. Otherwise, the size cannot be compared when the number of soldiers in different rows is equal.

To solve the code
Class Solution {public int[] kWeakestRows(int[][] mat, int k) { Use array to count the number of soldiers in each line and line mark, through calculation conversion to achieve a number to save the number of soldiers and line mark, directly call the system class sorting method to sort, take the first k after sorting // define combat array res, the length of the matrix of the number of lines int[] res = new int[mat.length]; For (int I = 0; i < mat.length; Int [] row = mat[I]; Int count = 0; For (int col: row) {if (1 == col) {// If (1 == col) { } // Number of soldiers * 100 + line number, assigned to the combat array res res[I] = count * 100 + I; } array.sort (res); Int [] nums = new int[k]; Nums for (int I = 0; i < k; ++ I) {// nums[I] = res[I] % 100; // nums[I] = res[I] % 100; } return nums; }}Copy the code
Submit the results

It took 1ms to execute, beating 98.36% of users in time, 39.6MB in memory consumption, and 24.46% in space.

As you can see, method 2 takes significantly less time to execute than method 1.

Methods 3

Method 2 can be optimized, and method 3 can be optimized on the basis of method 2.

Statistics of the number of soldiers per line can also continue to optimize, by binary search method to statistics, the execution time can also be reduced.

They say that soldier 1 must come before civilian 0, so the array is ordered, use binary search to quickly find the last 1, the last 1 corresponding to the row plus 1 is the number of soldiers in this row.

When we use binary search here, the details are a little bit different, not just looking for an element that’s equal to something, but also determining whether there’s a 1 after that element, and if there’s no 1 after that element, then we’ve found the corresponding element, and that element is the last one.

To solve the code
Class Solution {public int[] kWeakestRows(int[][] mat, int k) { Use array statistics of each line of the number of soldiers and line marks, statistics using binary search method, through calculation conversion to achieve a number to save the number of soldiers and line marks, directly call the system class sorting method for sorting, take the first k after sorting // define the combat effectiveness array res, Int [] res = new int[mat.length]; For (int I = 0; i < mat.length; Int [] row = mat[I]; Int left = 0; Int right = row.length - 1; int right = row.length - 1; // Define the middle pointer int center; Boolean isZero = true; // Binary search, but the details are a little different, not just to find the element equal to a certain value, but also to determine whether there is a 1 after the element, if there is no 1 after the element, then found the corresponding element, this element is the last 1, While (left <= right) {// Calculate the middle pointer center = (left + right) / 2; If (center == row.length - 1) {// If (center == row.length - 1) {// If (center == row.length - 1) {// If (center == row.length - 1) {// If (center == row.length - 1) { So its corresponding element is the last 1 // number of soldiers * 100 + line number, assigned to the combat power array res res[I] = (center + 1) * 100 + I; // The number of soldiers is not 0, the flag is set to false isZero = false; break; } if (0 == row[center + 1]) {// If (0 == row[center + 1]) {// If (0 == row[center + 1]) { Assign the value res[I] = (center + 1) * 100 + I; // The number of soldiers is not 0, the flag is set to false isZero = false; break; } // It is not the last 1, the binary array, zoom to the right, the middle pointer plus 1 assigned to the left pointer left = center + 1; } else {// If the element corresponding to the middle pointer is not equal to 1, the binary array is reduced to the left, and the middle pointer is reduced by 1. }} if (isZero) {// If (isZero) {// If (isZero) {// If (isZero) {// If (isZero) { Array.sort (res); Int [] nums = new int[k]; Nums for (int I = 0; i < k; ++ I) {// nums[I] = res[I] % 100; // nums[I] = res[I] % 100; } return nums; }}Copy the code
Submit the results

It took 1ms to execute, beating 98.36% of users in time, 39.6MB in memory consumption, and 12.81% of users in space.

Maybe the data range is not large enough, and the difference in running time is not significant.

Algorithm is summarized

There are two optimization points:

1, save the number of soldiers and sort can be optimized, by the number of soldiers * 100 + line mark, sort, and then mod 100, to replace the original transformation bubble sort.

Method 1 needs to use a list. The list element should use an array to store the number of soldiers and row symbols, and then transform bubble sort to sort the number of soldiers. After sorting, the row symbols in the list element are obtained and constructed into the first K row symbols.

Array. sort saves time and space by saving the number of soldiers * 100 + line labels to the array, and then calling the system class array. sort method to sort the array. The efficiency of this method is also more efficient than that of method 1 using bubble sort, because the sorting method of arrays. sort selects the appropriate sorting method according to the length and order degree of array, which is more efficient than method 1 using bubble sort only.

2. The number of soldiers per line can be optimized by binary search rather than direct violence traversal.

Methods 1 and 2 still use violence traversal to count the number of soldiers in each line, where the time complexity is O(n).

Method 3 is optimized to use binary search to count the number of soldiers in each row, because the problem says soldier 1 must come before civilian 0, so the array is ordered, so we can use binary search to quickly find the last 1, so as to calculate the number of soldiers in this row, here the time complexity becomes O(logN), It is an order of magnitude lower than the previous time complexity O(n).

The original link

The weakest K row in the matrix