题解 | #牧场奶牛集合区域#

牧场奶牛集合区域

https://www.nowcoder.com/practice/89218acf98234315af1cb3a223935318?tpId=354&tqId=10589478&ru=/exam/oj/ta&qru=/ta/interview-202-top/question-ranking&sourceUrl=%2Fexam%2Foj%2Fta%3FtpId%3D354

一、知识点:

双指针

二、文字分析:

使用两个指针 start 和 end 分别表示当前区间的起始位置和结束位置。遍历集合点编号数组时,如果当前集合点的编号与上一个集合点的编号连续,则更新当前区间的结束位置;否则,将当前区间的起始位置和结束位置加入结果中,并更新当前区间的起始位置和结束位置。最后,将最后一个区间的起始位置。

算法的时间复杂度为 O(n),空间复杂度为 O(m)。

三、编程语言:

java

四、正确代码:

import java.util.*;


public class Solution {
    /**
     * 找到覆盖所有编号的最小有序区间范围列表
     *
     * @param groups int整型一维数组,表示每头奶牛所在的集合点编号数组
     * @param n      int整型,表示集合点的总数
     * @return int整型二维数组,表示连续整数区间范围列表
     */
    public int[][] findGatheringAreas(int[] groups, int n) {
        ArrayList<int[]> result = new ArrayList<>();

        int start = groups[0]; // 当前区间的起始位置
        int end = groups[0]; // 当前区间的结束位置

        for (int i = 1; i < groups.length; i++) {
            // 如果当前集合点的编号连续,则更新当前区间的结束位置
            if (groups[i] == end + 1) {
                end = groups[i];
            } else {
                // 否则,将当前区间的起始位置和结束位置加入结果中
                result.add(new int[] {start, end});
                // 更新当前区间的起始位置和结束位置
                start = groups[i];
                end = groups[i];
            }
        }

        // 将最后一个区间的起始位置和结束位置加入结果中
        result.add(new int[] {start, end});

        // 将结果转换为二维数组并返回
        return result.toArray(new int[result.size()][2]);
    }
}

全部评论

相关推荐

重生我想学测开:嵌入式的问题,我准备入行京东外卖了
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务