'How to make this code faster in python (algorithm question)
Today I was browsing for some questions that I saw this: Algorithm - Air Battle
C ++ time limit: 1 second Java time limit: 2 seconds Python time limit: 10 seconds Memory limit: 256 MB
There are a number of fighters in a line, and all of them have different heights from the ground. Each fighter can only target its front fighters, provided that their height are less than the height of the fighter that is Under investigation.
The number of fighters that a fighter can target is called a strategic number. For example, if Fighter A can target 3 fighters, we say that the strategic number of Fighter A is 3.
Get the total strategic numbers of all the fighters.
Entraces: In the first line of input, n appears, which indicates the number of fighters. Then in the next line, the height of the n fighters comes in sequence from h_i.
0001≤n≤100 000
0001≤h≤100 000
Output:
In the output, print the sum of the strategic numbers of all the fighters.
Sample input 1:
5
5 4 3 7 6
Sample output 1 4
I wroted this code for it (in python) but the time limit will be passed in huge numbers:
n = int(input())
players = list(map(int, input().split()))
c = 0
for index, player in enumerate(players, 1):
c += len([num for num in players[index:] if num < player])
print(c)
Solution 1:[1]
The approach is largely similar to counting inversions in an array.
During the merge step, maintain two pointers (one for each half). Let the two elements from each being compared be i
(from the left half) and j
(right half). If i<j
, i
will also be smaller than all elements to the right of j
. You can accordingly increment i
's count, and move its pointer. This "hint" should be enough for you to implement a solution.
Sources
This article follows the attribution requirements of Stack Overflow and is licensed under CC BY-SA 3.0.
Source: Stack Overflow
Solution | Source |
---|---|
Solution 1 | Abhinav Mathur |