[LintCode] Interleaving Positive and Negative Numb

calx 发布于2019-08-14 15:22 / 1274人阅读

摘要：注意，若正数多于负数，则序列以正数开始，正数结束。所以先统计正数个数，若超过序列长度的一半，则正指针从开始，反之则负指针从开始。注意交换函数的形式，必须是交换指针所指数字的值，而非坐标。

Problem

Given an array with positive and negative integers. Re-range it to interleaving with positive and negative integers.

Notice

You are not necessary to keep the original order of positive integers or negative integers.

Example

Given [-1, -2, -3, 4, 5, 6], after re-range, it will be [-1, 5, -2, 4, -3, 6] or any other reasonable answer.

Challenge

Do it in-place and without extra memory.

Note

典型双指针题目，两个指针分别指向交叉的正数和负数。
注意，若正数多于负数，则序列以正数开始，正数结束。所以先统计正数个数，若超过序列长度的一半，则正指针从0开始，反之则负指针从0开始。指针每次跳两位，若指向的数字符号不符，则停止，交换两指针指向的数。
注意交换函数swap()的形式，必须是交换指针所指数字的值，而非坐标。所以下面这样的写法是不对的：swap(A[posIndex], A[negIndex])，因为它调用的是swap(integerA, integerB)，在交换值的同时也交换了坐标。

Solution

class Solution {
    public void rerange(int[] A) {
        int posNum = 0, posIndex = 1, negIndex = 0;
        for (int a : A) {
            posNum += a > 0 ? 1 : 0;
        }
        if (posNum * 2 > A.length) {
            posIndex = 0;
            negIndex = 1;
        }
        while (posIndex < A.length && negIndex < A.length) {
            while (posIndex < A.length && A[posIndex] > 0) posIndex += 2;
            while (negIndex < A.length && A[negIndex] < 0) negIndex += 2;
            if (posIndex < A.length && negIndex < A.length) {
                swap(A, posIndex, negIndex);
                posIndex += 2;
                negIndex += 2;
            }
        }
    }
    public void swap(int[] A, int i, int j) {
        int temp = A[i];
        A[i] = A[j];
        A[j] = temp;
    }
}

海外云主机私有云 Negative Positive Interleaving LintCode

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/65718.html

[LintCode] First Missing Positive

摘要：找第一个缺失的正整数，只要先按顺序排列好，也就是，找到第一个和不对应的数就可以了。注意数组的从开始，而正整数从开始，所以重写排列的时候要注意换成，而就是从开始的数组中的元素。 Problem Given an unsorted integer array, find the first missing positive integer. Example Given [1,2,0] re...

snifes 2019-08-14 15:20 评论0 收藏0
[LintCode] Big Integer Addition

Problem Given two non-negative integers num1 and num2 represented as string, return the sum of num1 and num2. Notice The length of both num1 and num2 is < 5100.Both num1 and num2 contains only digits ...

i_garfileo 2019-08-16 10:59 评论0 收藏0
[LintCode] Backpack I II III IV V VI [背包六问]

摘要：单次选择最大体积动规经典题目，用数组表示书包空间为的时候能装的物品最大容量。注意的空间要给，因为我们要求的是第个值，否则会抛出。依然是以背包空间为限制条件，所不同的是取的是价值较大值，而非体积较大值。 Backpack I Problem 单次选择+最大体积 Given n items with size Ai, an integer m denotes the size of a b...

sutaking 2019-08-14 14:31 评论0 收藏0
[LintCode] Minimum Size Subarray Sum

摘要：做一个窗口，满足的左界到右界的距离最小值为所求。循环的约束条件要注意，不要遗漏不能超过的长度，但可以等于，因为存在所有元素之和为的极端情况。在时，先更新窗口为当前循环后的最小值，减去最左元素，指针后移。 Problem Given an array of n positive integers and a positive integer s, find the minimal len...

hyuan 2019-08-14 15:16 评论0 收藏0
[LintCode/LeetCode] Combination Sum I & II

摘要：和唯一的不同是组合中不能存在重复的元素，因此，在递归时将初始位即可。 Combination Sum I Problem Given a set of candidate numbers (C) and a target number (T), find all unique combinations in C where the candidate numbers sums to T...

ThreeWords 2019-08-14 15:23 评论0 收藏0