144 · 交错正负数（partition）

链接：LintCode 炼码

题解：九章算法 - 帮助更多程序员找到好工作，硅谷顶尖IT企业工程师实时在线授课为你传授面试技巧

class Solution { public: /** * @param a: An integer array. * @return: nothing */ void rerange(vector<int> &a) { // write your code here if (a.size() <= 0) { return; } int fushu = 0; int zhengshu = 0; for_each(a.begin(), a.end(), [&fushu, &zhengshu](int num) { if (num > 0) { ++zhengshu; } else if (num < 0) { ++fushu; } }); int left = 0; int right = a.size()-1; int flag = fushu > zhengshu ? 1 : -1; // 让数量多的元素排在左边 while (left <= right) { while (left <= right && a[left] * flag < 0) { ++left; } while (left <= right && a[right] * flag > 0) { --right; } if (left <= right) { swap(a[left], a[right]); ++left; --right; } } // 默认是排除第0个元素 left = 1; right = a.size() - 1; // 如果负数数量和正数数量相等，则右边也减少一个元素 if (fushu == zhengshu) { right = a.size() - 2; } // 交换交替 while (left <= right) { swap(a[left], a[right]); left += 2; right -= 2; } } };

public class Solution { public void rerange(int[] A) { int pos = 0, neg = 0; for (int i = 0; i < A.length; i++) { if (A[i] > 0) { pos++; } else { neg++; } } partition(A, pos > neg); interleave(A, pos == neg); } private void partition(int[] A, boolean startPositive) { int flag = startPositive ? 1 : -1; int left = 0, right = A.length - 1; while (left <= right) { while (left <= right && A[left] * flag > 0) { left++; } while (left <= right && A[right] * flag < 0) { right--; } if (left <= right) { int temp = A[left]; A[left] = A[right]; A[right] = temp; left++; right--; } } } private void interleave(int[] A, boolean has_same_length) { int left = 1, right = A.length - 1; if (has_same_length) { right = A.length - 2; } while (left < right) { int temp = A[left]; A[left] = A[right]; A[right] = temp; left += 2; right -= 2; } } }