LeetCode 1560. The sector with the most passes on the circular track

1560. The most frequent sector on a circular track

Give you an integer n And an array of integers rounds . There is a circular track made up of n Sectors make up , Sector number from 1 To n . Now a marathon will be held on this track , The marathon is run by m There are three stages . among , The first i The next stage will be from sector rounds[i - 1] Start , To sector rounds[i] end . for instance , The first 1 Stage from rounds[0] Start , To rounds[1] end .

Please return the sectors that have passed the most times in the form of array , By sector number Ascending array .

Be careful , The track forms a circle counterclockwise in ascending order of sector number （ See the first example ）.

Example 1：

 Input ：n = 4, rounds = [1,3,1,2]
 Output ：[1,2]
 explain ： This marathon starts from  1  Start . The order of passing through each sector is as follows ：
1 --> 2 --> 3（ Stage  1  end ）--> 4 --> 1（ Stage  2  end ）--> 2（ Stage  3  end , That is, the end of the Marathon ）
 among , A sector  1  and  2  Twice , They are the two sectors that have passed the most times . A sector  3  and  4  Only once .

Example 2：

 Input ：n = 2, rounds = [2,1,2,1,2,1,2,1,2]
 Output ：[2]

Example 3：

 Input ：n = 7, rounds = [1,3,5,7]
 Output ：[1,2,3,4,5,6,7]

Tips ：

• 2 <= n <= 100
• 1 <= m <= 100
• rounds.length == m + 1
• 1 <= rounds[i] <= n
• rounds[i] != rounds[i + 1] , among 0 <= i < m

Two 、 Method 1

simulation

class Solution {
    
    public List<Integer> mostVisited(int n, int[] rounds) {
    
        List<Integer> res = new ArrayList<>();
        int start = rounds[0];
        int end = rounds[rounds.length - 1];
        if (start <= end) {
    
            for (int i = start; i <= end; i++) {
    
                res.add(i);
            }
        } else {
    
            for (int i = 1; i <= end; i++) {
    
                res.add(i);
            }
            for (int i = start; i <= n; i++) {
    
                res.add(i);
            }
        }
        return res;
    }
}

Complexity analysis

• Time complexity ：O(N). Maximum distance between start point and end point N-1 Sectors .

• Spatial complexity ：O(1). In addition to the answer array , We only need constant space to store several variables .