# leetcode 1560. Most Visited Sector in a Circular Track（python）

2022-01-31 13:33:25

「 This is my participation 11 The fourth of the yuegengwen challenge 13 God , Check out the activity details ：2021 One last more challenge

### describe

Given an integer n and an integer array rounds. We have a circular track which consists of n sectors labeled from 1 to n. A marathon will be held on this track, the marathon consists of m rounds. The ith round starts at sector rounds[i - 1] and ends at sector rounds[i]. For example, round 1 starts at sector rounds and ends at sector rounds

Return an array of the most visited sectors sorted in ascending order.

Notice that you circulate the track in ascending order of sector numbers in the counter-clockwise direction (See the first example).

Example 1: ``````Input: n = 4, rounds = [1,3,1,2]
Output: [1,2]
Explanation: The marathon starts at sector 1. The order of the visited sectors is as follows:
1 --> 2 --> 3 (end of round 1) --> 4 --> 1 (end of round 2) --> 2 (end of round 3 and the marathon)
We can see that both sectors 1 and 2 are visited twice and they are the most visited sectors. Sectors 3 and 4 are visited only once.
Copy code ``````

Example 2:

``````Input: n = 2, rounds = [2,1,2,1,2,1,2,1,2]
Output: 
Copy code ``````

Example 3:

``````Input: n = 7, rounds = [1,3,5,7]
Output: [1,2,3,4,5,6,7]
Copy code ``````

Note:

``````2 <= n <= 100
1 <= m <= 100
rounds.length == m + 1
1 <= rounds[i] <= n
rounds[i] != rounds[i + 1] for 0 <= i < m
Copy code ``````

### analysis

According to the meaning , Given an integer n And an array of integers rounds . We have a circular track , It consists of n The marks are 1 To n Sector composition of . The marathon will be held on this track , Marathon runs counter clockwise m round . The first i Wheel slave sector rounds[i - 1] Start , To sector rounds[i] end . for example , The first 1 Wheel slave sector rounds Start and in sector rounds end , The title requires us to return the most visited sector array sorted in ascending order .

The idea is simple , It's running around the track counterclockwise , Find the sector that has passed the most times , We can think of this circular track as a straight track , The maximum number of rounds you can run is len(rounds) , If we n=4 , rounds = [2,3,1,2] , We can turn the track into the following form ：

``````[1,2,3,4,1,2,3,4,1,2,3,4,1,2,3,4]
Copy code ``````

So let's find the starting position first 2, And will 2 Remove all the preceding numbers , At this point, the track becomes ：

``````[2,3,4,1,2,3,4,1,2,3,4,1,2,3,4]
Copy code ``````

At this point, we just need to find out what happened 2 、3 、1 、2 The number of times of four numbers is enough , This is the case ：

``````1  After  1  Time
2  After  2  Time
3  After  1  Time
4  After  1  Time
Copy code ``````

Finally, find the number that has passed the most times to form a list , Return in ascending order .

``````class Solution(object):
def mostVisited(self, n, rounds):
"""
:type n: int
:type rounds: List[int]
:rtype: List[int]
"""
L = [i for i in range(1, n + 1)] * (len(rounds))
d = {i: 0 for i in range(1, n + 1)}
for i in range(L.index(rounds)):
L.pop(0)
for pos in rounds[1:]:
i = L.index(pos)
for j in range(i + 1):
d[L.pop(0)] += 1
result = [k for k, v in d.items() if v == max(d.values())]
result.sort()
return result

Copy code ``````

### Running results

``````Runtime: 168 ms, faster than 8.82% of Python online submissions for Most Visited Sector in a Circular Track.
Memory Usage: 13.6 MB, less than 8.82% of Python online submissions for Most Visited Sector in a Circular Track.
Copy code ``````

### analysis

In fact, the above simulation method is clumsy , I saw the master's solution , You just need to find the rules and find that the sector with the most frequent access is only related to / The end position is related to , The answer can be found through simple calculation .

``````class Solution(object):
def mostVisited(self, n, rounds):
"""
:type n: int
:type rounds: List[int]
:rtype: List[int]
"""
start=rounds
end=rounds[-1]
result=[]
if(start>end):
for i in range(end):
result.append(i+1)
for i in range(start,n+1):
result.append(i)
else:
for i in range(start,end+1):
result.append(i)
return result
Copy code ``````

### Running results

``````Runtime: 32 ms, faster than 67.65% of Python online submissions for Most Visited Sector in a Circular Track.
Memory Usage: 13.3 MB, less than 94.12% of Python online submissions for Most Visited Sector in a Circular Track.
Copy code ``````