当前位置:  首页>> 技术小册>> 数据结构与算法(中)

难度:
Hard

题意:

  1. 给n个矩阵,求这n个矩阵覆盖的区域面积有多大

思路:

  • 把x坐标和y坐标id化,将n个矩阵覆盖的区域分成r*c个小矩阵,这些小矩阵的距离都可以不相等
  • 遍历所有的矩阵,把这些小矩阵填充满
  • 遍历小矩阵,统计面积
  • 复杂度是o(n^3)
  • 这个题目可以将x坐标id化后,构建线段树来查询和更新面积区域,复杂度可以降为o(n^2logn),当n>=1000使用

代码:

  1. class Solution {
  2. private int[] setToArray(TreeSet<Integer> set) {
  3. int[] ret = new int[set.size()];
  4. int idx = 0;
  5. for (Integer e: set) {
  6. ret[idx++] = e;
  7. }
  8. return ret;
  9. }
  10. private static int MOD = 1000000007;
  11. public int rectangleArea(int[][] rectangles) {
  12. TreeSet<Integer> set = new TreeSet<Integer>();
  13. for (int i = 0;i < rectangles.length;i++) {
  14. set.add(rectangles[i][0]);
  15. set.add(rectangles[i][2]);
  16. }
  17. int[] x = setToArray(set);
  18. set.clear();
  19. for (int i = 0;i < rectangles.length;i++) {
  20. set.add(rectangles[i][1]);
  21. set.add(rectangles[i][3]);
  22. }
  23. int[] y = setToArray(set);
  24. boolean[][] area = new boolean[x.length][y.length];
  25. for (int i = 0;i < x.length;i++) {
  26. for (int j = 0;j < y.length;j++) {
  27. area[i][j] = false;
  28. }
  29. }
  30. for (int i = 0;i < rectangles.length;i++) {
  31. int lx = Arrays.binarySearch(x, rectangles[i][0]);
  32. int rx = Arrays.binarySearch(x, rectangles[i][2]);
  33. int ly = Arrays.binarySearch(y, rectangles[i][1]);
  34. int ry = Arrays.binarySearch(y, rectangles[i][3]);
  35. for (int j = lx;j < rx;j++) {
  36. for (int k = ly;k < ry;k++) {
  37. area[j][k] = true;
  38. }
  39. }
  40. }
  41. int ret = 0;
  42. for (int i = 0;i < x.length;i++) {
  43. for (int j = 0;j < y.length;j++) {
  44. if (area[i][j]) {
  45. ret += (long)(x[i + 1] - x[i]) * (y[j + 1] - y[j]) % MOD;
  46. if (ret >= MOD) {
  47. ret -= MOD;
  48. }
  49. }
  50. }
  51. }
  52. return ret;
  53. }
  54. }

该分类下的相关小册推荐: