# 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[0] and ends at sector rounds[1]

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: [2]
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[0] Start and in sector rounds[1] 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[0])):
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[0]
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 ``````