[leetcode/lintcode 题解] 字节跳动面试题：01交换

描述
给定一个只包含0，1两个元素的数组，只能交换相邻的元素使这个数组升序(即所有的0都在1的左边)，返回最少交换次数。

• 1 <= n <= 10^4

在线评测地址：领扣题库官网

样例1
示例1:

输入: 
nums = [1,0,1,1,0,0,0,1]
输出: [0,0,0,0,1,1,1,1]

示例 2:

输入: 
nums = [0, 0, 0, 1, 1]
输出: 0

同向双指针版
从右边开始往左。 i = right, j = left。 i需要停在0上面， j需要找到1， 然后记录交换的次数。 需要注意的是， 当交换完了以后， 原先的1就变成0了， 那么i就不能再跳过了， 那个时候， 需要处理下

class Solution:
    """
    @param nums: an Integer array
    @return: return the minimum number of swaps.
    """
    def SwapZeroOne(self, nums):
        j = len(nums) - 2
        num_swaps = 0
        exchanged = set()
        for i in range(len(nums) - 1, -1, -1):
            if i not in exchanged and nums[i] == 1:
                continue
            j = min(j, i - 1)
            while j >= 0 and nums[j] == 0:
                j -= 1
            if j >= 0 and nums[j] == 1:
                print(i, j)
                num_swaps += i - j
                exchanged.add(j)
            j -= 1
        return num_swaps

更多题解参考：九章官网solution