Compute The Number of Intersections in a Sequence of Discs in Java

2025 年 5 月 6 日 | 阅读 8 分钟

这是Google、Amazon、TCS、Accenture、Flipkart等顶级IT公司面试中经常遇到的问题。通过解决这个问题，可以考察面试者的逻辑能力、批判性思维和解决问题的能力。因此，在本节中，我们将用不同的方法和逻辑在 Java 中计算圆盘序列中的交点数。我们还将创建相应的 Java 程序。

问题定义

给定一个数组 A，其中每个元素 A[i] 表示以位置 i 为圆心的圆盘的半径。您的任务是计算相交圆盘对的数量。

半径为 A[i] 的圆盘覆盖区间 [i - A[i], i + A[i]]。
如果它们的区间重叠，则两个圆盘相交。

蛮力法

代码中使用的方法是带有排序的蛮力法，其中首先对圆盘的边界进行排序。然后，将所有圆盘对进行比较，以根据它们的边界检查相交情况。

顶部表单

底部表单

算法

步骤 1：初始化两个数组 leftBoundaries 和 rightBoundaries，用于存储每个圆盘的最左边界和最右边界。

步骤 2：遍历 radiusArray，对于每个索引 i 处的圆盘

计算 leftBoundaries[i] = i - radiusArray[i]。
计算 rightBoundaries[i] = i + radiusArray[i]。

步骤 3：将 leftBoundaries 和 rightBoundaries 数组都按升序排序。

步骤 4：将 intersectionCount 初始化为零。

步骤 5：对于每个圆盘 i

将其与所有后续圆盘 j > i 进行比较。
如果 rightBoundaries[i] >= leftBoundaries[j]，则增加 intersectionCount。

步骤 6：如果在任何时候 intersectionCount 超过 10,000,000，则返回 -1。

步骤 7：完成所有比较后，返回相交的总数（intersectionCount）。

实施

文件名：NumberOfIntersection.java

import java.util.*;
class NumberOfIntersection {
    public int solution(int[] radiusArray) {
        long[] leftBoundaries = new long[radiusArray.length];
        long[] rightBoundaries = new long[radiusArray.length];
        for (int i = 0; i < radiusArray.length; i++) {
            leftBoundaries[i] = (long) i - radiusArray[i];
            rightBoundaries[i] = (long) i + radiusArray[i];
        }
        Arrays.sort(leftBoundaries);
        Arrays.sort(rightBoundaries);
        int intersectionCount = 0;
        for (int i = 0; i < radiusArray.length - 1; i++) {
            for (int j = i + 1; j < radiusArray.length && rightBoundaries[i] >= leftBoundaries[j]; j++) {
                intersectionCount++;
                if (intersectionCount > 10000000)
                    return -1;
            }
        }
        return intersectionCount;
    }
    // Main method to run the program
    public static void main(String[] args) {
        Solution solution = new Solution(); 
        // Example input: array representing disc radii
        int[] radiusArray = {1, 5, 2, 1, 4, 0};
        // Call the solution method and print the result
        System.out.println(solution.solution(radiusArray));  // Expected output: 11
    }
}   

输出

时间复杂度：O(n^2)

空间复杂度：O(n)

使用扫描线方法

扫描线算法是一种高效的计算几何技术，用于通过将一条线“扫过”平面并按排序顺序处理事件来解决涉及平面上的区间或事件的问题。它通过维护活动的区间或对象来降低时间复杂度，从而在直线前进时能够有效地计算相交数或处理事件。

算法

步骤 1：计算圆盘数 n 并初始化 left 和 right 数组以存储边界。

步骤 2：对于每个圆盘，计算 left[i] = i - A[i] 和 right[i] = i + A[i]。

步骤 3：对 left 和 right 数组进行排序。

步骤 4：遍历圆盘

移除已结束的圆盘 (right[j] < left[i])。
计算与活动圆盘的相交数。
将当前圆盘添加到活动圆盘中。

步骤 5：如果相交数超过 10,000,000，则返回 -1；否则，返回总数。

实施

文件名：DiscIntersections.java

import java.util.*;
public class DiscIntersections {
    public int countIntersections(int[] A) {
        int n = A.length;  // Get the number of discs
        // Arrays to store the left and right boundaries of each disc
        long[] left = new long[n];  // 'left[i]' is the leftmost point covered by the i-th disc
        long[] right = new long[n]; // 'right[i]' is the rightmost point covered by the i-th disc
        // Calculate the left and right ends for each disc
        for (int i = 0; i < n; i++) {
            // Left endpoint is the center (i) minus the radius (A[i])
            left[i] = i - (long) A[i];
            // Right endpoint is the center (i) plus the radius (A[i])
            right[i] = i + (long) A[i];
        }
        // Sort both the left and right endpoint arrays
        Arrays.sort(left);  // Sort left endpoints in increasing order
        Arrays.sort(right); // Sort right endpoints in increasing order
        int intersections = 0; // Initialize the count of intersections
        int activeDiscs = 0;   // Tracks the number of active discs (discs that have started but not ended)
        int j = 0;             // Pointer for the right array to manage disc ends
        // Iterate over each disc's left endpoint
        for (int i = 0; i < n; i++) {
            // Check if there are discs that have ended before the current disc's left boundary
            // We move the 'j' pointer to the first disc that has not yet ended
            while (j < n && right[j] < left[i]) {
                activeDiscs--;  // Decrease the count of active discs as they have ended
                j++;            // Move to the next right endpoint
            }
            // The number of currently active discs before this one started is the number of intersections
            intersections += activeDiscs;
            // Add the current disc to the active discs count
            activeDiscs++;
            // If the number of intersections exceeds 10,000,000, return -1 as per problem constraints
            if (intersections > 10000000) {
                return -1;  // Early exit if too many intersections
            }
        }
        // Return the total number of intersections found
        return intersections;
    }
    public static void main(String[] args) {
        DiscIntersections di = new DiscIntersections();
        // Example input: Array A where A[i] is the radius of the i-th disc
        int[] A = {1, 5, 2, 1, 4, 0};
        // Call the function to count intersections and print the result
        System.out.println(di.countIntersections(A));  // Expected output: 11
    }
}   

输出

时间复杂度：O(nlog n)，其中 n 是圆盘的数量（由于对端点进行排序）。

空间复杂度：O(n)，因为我们使用数组来存储左右端点。

使用线段树或 Fenwick 树（二叉索引树）方法

使用线段树或 Fenwick 树（二叉索引树）涉及利用这些数据结构来有效地管理和查询活动圆盘的数量。

算法

步骤 1：找到每个圆盘的 left (i-A[i]i - A[i]i-A[i]) 和 right (i+A[i]i + A[i]i+A[i]) 边界。

步骤 2：将所有唯一的边界映射到较小的索引。

步骤 3：初始化一个范围树来管理活动范围。

步骤 4：查询每个圆盘的右边界的重叠，并在树中更新活动范围。

步骤 5：返回相交数，如果相交数超过 10710^7107，则返回 -1。

实施

文件名：DiscIntersectionCalculator.java

import java.util.*;  // Importing necessary utility classes
class DiscIntersectionCalculator {
    // RangeTree class to handle range updates and queries efficiently
    static class RangeTree {
        private int[] tree;  // Array to store segment tree data
        private int size;     // Size of the segment tree
        // Constructor to initialize the range tree with given size
        public RangeTree(int n) {
            size = n;  // Setting the size
            tree = new int[4 * n];  // Allocating space for the range tree array
        }
        // Update method to increment values in the range [l, r] by 'value'
        public void update(int idx, int start, int end, int l, int r, int value) {
            if (r < start || l > end) return;  // If range is outside the current node, do nothing
            if (l <= start && end <= r) {  // If current range is fully within [l, r]
                tree[idx] += value;  // Update the current node
                return;
            }
            int mid = (start + end) / 2; 
            // Recursively update left child
            update(2 * idx + 1, start, mid, l, r, value);
            // Recursively update right child
            update(2 * idx + 2, mid + 1, end, l, r, value);
        }
        // Query method to get the value at position 'pos'
        public int query(int idx, int start, int end, int pos) {
            if (start == end) return tree[idx]; 
            int mid = (start + end) / 2; 
            if (pos <= mid)  // If 'pos' lies in the left child
                return tree[idx] + query(2 * idx + 1, start, mid, pos);  // Add current node's value and query left child
            else  // If 'pos' lies in the right child
                return tree[idx] + query(2 * idx + 2, mid + 1, end, pos);  // Add current node's value and query right child
        }
    }
    // Method to calculate the number of intersections between discs
    public int calculateIntersections(int[] A) {
        int n = A.length;  // Length of input array A
        long[] leftBoundaries = new long[n];  // Array to store the left boundaries of the discs
        long[] rightBoundaries = new long[n];  // Array to store the right boundaries of the discs
        // Calculating the left and right boundaries for each disc
        for (int i = 0; i < n; i++) {
            leftBoundaries[i] = i - (long) A[i];  // Left boundary for disc i
            rightBoundaries[i] = i + (long) A[i];  // Right boundary for disc i
        }
        // TreeSet to store all unique boundary points (left and right)
        TreeSet<Long> allPoints = new TreeSet<>();
        for (long x : leftBoundaries) allPoints.add(x);  // Add all left boundaries
        for (long x : rightBoundaries) allPoints.add(x);  // Add all right boundaries
        // Map to assign each unique boundary point an index for coordinate compression
        Map<Long, Integer> coordinateIndex = new HashMap<>();
        int index = 0;  // Start with index 0
        for (long point : allPoints) coordinateIndex.put(point, index++);  // Assign a unique index to each point
        // Create a range tree for the range of compressed coordinates
        RangeTree rangeTree = new RangeTree(index);
        int intersectionCount = 0;  // Initialize intersection count to 0
        // For each disc, calculate the number of intersections
        for (int i = 0; i < n; i++) {
            int left = coordinateIndex.get(leftBoundaries[i]);  // Get compressed index of left boundary
            int right = coordinateIndex.get(rightBoundaries[i]);  // Get compressed index of right boundary
            intersectionCount += rangeTree.query(0, 0, index - 1, right);  // Query the range tree for the number of intersections at 'right'
            rangeTree.update(0, 0, index - 1, left, right, 1); 
        }
        if (intersectionCount > 10000000) return -1;
        return intersectionCount;  // Return the total intersection count
    }
    // Main method to test the disc intersection calculator with a sample input
    public static void main(String[] args) {
        DiscIntersectionCalculator calculator = new DiscIntersectionCalculator();  // Create a DiscIntersectionCalculator object
        int[] A = {1, 5, 2, 1, 4, 0};  // Example input array
        System.out.println(calculator.calculateIntersections(A));
    }
}   

输出

时间复杂度：O(nlogn)

辅助空间： O(n)

下一主题Java 中的幸运数字

Compute The Number of Intersections in a Sequence of Discs in Java

问题定义

蛮力法

算法

实施

使用扫描线方法

算法

实施

使用线段树或 Fenwick 树（二叉索引树）方法

算法

实施

联系信息

关注我们

教程

面试题

在线编译器

Python

Java

.Net Framework

AI, ML and Data Science

Cloud Technology

B.Tech and MCA

Web Technology

PHP

Software Testing

Technical Interview

Java Interview

Python

Web Interview

Database Interview

B.Tech / MCA

Important Interview

Software Testing Interview

Company Interviews

Online Compilers

Multiple Choice Questions

Java Conversion

Java Misc

Compute The Number of Intersections in a Sequence of Discs in Java

问题定义

蛮力法

算法

实施

使用扫描线方法

算法

实施

使用线段树或 Fenwick 树（二叉索引树）方法

算法

实施

相关帖子

Java 中 Iterator 和 ListIterator 的区别及示例

Java 中打印数字中包含 1、2 和 3 的升序数字

Moser-De-Bruijn Sequence in Java

Java Graph

如何在 Java 中创建表

将字符串列表转换为逗号分隔的字符串（Java）

如何在 Java 中将 double 转换为 string

Java 中的文件描述符类

Java 中的序数

使用 Java 查找数组中缺失的数字

订阅 Tpoint Tech

联系信息

关注我们

教程

面试题

在线编译器