This article is participating in the “Java Theme Month – Java Brush questions punch card”, see the activity link for details

1. Title Description

2. How to solve the problem

Enumeration of violence

Enumerating violence always solves the problem. First compute the xOR value of each coordinate and then sort to find the k major xor value.

Time complexity analysis

  • O(1+mn)nm/2)=O((mn)^2)
  • Sorting (fast sorting) : O(mnlogmn)

Spatial complexity analysis

  • Required nm space to store xOR value: O(mn)

2. Optimize xOR calculation – prefix sum

We found that calculating xOR was a bottleneck. How do we optimize it? We find that violence enumerations double count xor of two numbers each time. Can we record these historical values? The answer is yes. Xor operations satisfy the commutative law:

A radius b = b the radiusCopy the code

And associative law:

(a radius b) radius c = a radius radius (b c)Copy the code

Another property is that two identical numbers will cancel each other out:

The radius radius y y = x xCopy the code

According to the above properties, we can obtain the prefix and calculation formula:

The pre (I, j) = pre (I - 1, j) radius pre (I, j - 1) the radius pre (I - 1, j - 1) the radius matrix (I, j)Copy the code

Time complexity analysis

  • Calculate xOR value: O(Mn)
  • Sorting (fast sorting) : O(mnlogmn)

Spatial complexity analysis

  • Required nm space to store xOR value: O(mn)

3. Optimize k large selection – fast selection algorithm

We found that sorting became a bottleneck, so how do we optimize it? 215. the KTH largest element in an array. Yes, we can use quicksort to find large k values in sorting. Specific details will be analyzed in the next article.

Time complexity analysis

  • Calculate xOR value: O(Mn)
  • Fast selection (fast sorting) : average O(MN)

Spatial complexity analysis

  • Required nm space to store xOR value: O(mn)

Three, code implementation

class Solution { public int kthLargestValue(int[][] matrix, int k) { int m = matrix.length, n = matrix[0].length; int[][] pre = new int[m + 1][n + 1]; List<Integer> results = new ArrayList<Integer>(); for (int i = 1; i <= m; ++i) { for (int j = 1; j <= n; ++j) { pre[i][j] = pre[i - 1][j] ^ pre[i][j - 1] ^ pre[i - 1][j - 1] ^ matrix[i - 1][j - 1]; results.add(pre[i][j]); } } nthElement(results, 0, k - 1, results.size() - 1); return results.get(k - 1); } public void nthNum(List<Integer> results, int left, int kth, int right) { if (left == right) { return; } int pivot = (int) (left + Math.random() * (right - left + 1)); swap(results, pivot, right); int sepl = left - 1, sepr = left - 1; for (int i = left; i <= right; i++) { if (results.get(i) > results.get(right)) { swap(results, ++sepr, i); swap(results, ++sepl, sepr); } else if (results.get(i) == results.get(right)) { swap(results, ++sepr, i); } } if (sepl < left + kth && left + kth <= sepr) { return; } else if (left + kth <= sepl) { nthNum(results, left, kth, sepl); } else { nthNum(results, sepr + 1, kth - (sepr - left + 1), right); } } public void swap(List<Integer> results, int index1, int index2) { int temp = results.get(index1); results.set(index1, results.get(index2)); results.set(index2, temp); }}Copy the code