[LintCode] Interleaving Positive and Negative Numb

calx 發布于2019-08-14 15:22 / 1383人閱讀

摘要：注意，若正數多于負數，則序列以正數開始，正數結束。所以先統計正數個數，若超過序列長度的一半，則正指針從開始，反之則負指針從開始。注意交換函數的形式，必須是交換指針所指數字的值，而非坐標。

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;
    }
}

GPU云服務器云服務器 Negative Positive Interleaving LintCode

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://m.specialneedsforspecialkids.com/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