LC: 1151. Minimum Swaps to Group All 1's Together
https://leetcode.com/problems/minimum-swaps-to-group-all-1s-together/
1151. Minimum Swaps to Group All 1's Together
Given a binary array data, return the minimum number of swaps required to group all 1’s present in the array together in any place in the array.
Example 1:
Input: data = [1,0,1,0,1]
Output: 1
Explanation:
There are 3 ways to group all 1's together:
[1,1,1,0,0] using 1 swap.
[0,1,1,1,0] using 2 swaps.
[0,0,1,1,1] using 1 swap.
The minimum is 1.Example 2:
Input: data = [0,0,0,1,0]
Output: 0
Explanation:
Since there is only one 1 in the array, no swaps needed.Example 3:
Input: data = [1,0,1,0,1,0,0,1,1,0,1]
Output: 3
Explanation:
One possible solution that uses 3 swaps is [0,0,0,0,0,1,1,1,1,1,1].Example 4:
Constraints:
1 <= data.length <= 105data[i]is0or1.
1151. Minimum Swaps to Group All 1's Together
The Essence:
In dem angegebenen Array müssen alle 1-Werte zusammen gruppiert werden. Das ist logisch äquivalent zu der Aussage, dass sich alle 1-Werte in einem gegebenen Intervall im Array befinden sollten, dessen Länge die Anzahl der 1-Werte ist. Die minimalen Täusche sind dann die Anzahl der 0’s in diesem Intervall. Wir sollen dann das Intervall mit minimaler Anzahl der 0’s finden.
Details:
In einer ersten Schleife kann die Anzahl der 1’s gezählt werden. Die Anzahl der 0’s in jedem Intervall kann überprüft werden, indem man Präfixsummen verwendet oder in der Schleife neue und aktuelle Werte mit der aktuellen Gesamtsumme vergleicht.
Solution(s) and Further Explanation:
Default Code:
Last updated