algorithm - 排列数组中的数字以使所有负值出现在所有正值之前，最少需要多少次交换？

Question

假设我们想要排列存储在任何数组中的 n 个数字，使得所有负值都出现在所有正值之前。那么如何找到在最坏情况下所需的最小交换次数？

标签： algorithm

Answer 1

您可以使用两个指针方法。

1. 首先将所有负数移动到位并计算所需的交换次数

2. 将最后的所有负数移动到位并计算所需的交换次数

3. 比较这些交换次数以获得最小交换次数。

这是 C++ 实现：

    int minimumExchange(vector<int>& arr) {
        int result = INT_MAX;
        int countFirst = 0, countLast = 0;
        int n = arr.size();
        vector<int> tmp(arr); 

        int left = 0, right = 0;
        while(right < n) {
            if(arr[right] < 0) {
               swap(arr[left], arr[right]);
               if(left != right) countFirst++;
               left++;
            }
            right++;
        }

        arr = tmp;
        left = n - 1, right = n - 1;
        while(right >= 0) {
            if(arr[right] < 0) {
               swap(arr[left], arr[right]);
               if(left != right) countLast++;
               left--;
            }
            right--;
        }
        result = min(countFirst, countLast);
        return result;
    }

你可以在这里找到工作代码。

时间复杂度是O(n)数组n的大小。