資訊專欄INFORMATION COLUMN
摘要：注意，若正數(shù)多于負(fù)數(shù)，則序列以正數(shù)開始，正數(shù)結(jié)束。所以先統(tǒng)計(jì)正數(shù)個(gè)數(shù)，若超過序列長(zhǎng)度的一半，則正指針從開始，反之則負(fù)指針從開始。注意交換函數(shù)的形式，必須是交換指針?biāo)笖?shù)字的值，而非坐標(biāo)。
Problem
Given an array with positive and negative integers. Re-range it to interleaving with positive and negative integers.
NoticeYou are not necessary to keep the original order of positive integers or negative integers.
ExampleGiven [-1, -2, -3, 4, 5, 6], after re-range, it will be [-1, 5, -2, 4, -3, 6] or any other reasonable answer.
ChallengeDo it in-place and without extra memory.
Note典型雙指針題目，兩個(gè)指針分別指向交叉的正數(shù)和負(fù)數(shù)。
注意，若正數(shù)多于負(fù)數(shù)，則序列以正數(shù)開始，正數(shù)結(jié)束。所以先統(tǒng)計(jì)正數(shù)個(gè)數(shù)，若超過序列長(zhǎng)度的一半，則正指針從0開始，反之則負(fù)指針從0開始。指針每次跳兩位，若指向的數(shù)字符號(hào)不符，則停止，交換兩指針指向的數(shù)。
注意交換函數(shù)swap()的形式，必須是交換指針?biāo)笖?shù)字的值，而非坐標(biāo)。所以下面這樣的寫法是不對(duì)的：swap(A[posIndex], A[negIndex])，因?yàn)樗{(diào)用的是swap(integerA, integerB)，在交換值的同時(shí)也交換了坐標(biāo)。
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;
}
}
文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請(qǐng)注明本文地址：http://systransis.cn/yun/65718.html
摘要：找第一個(gè)缺失的正整數(shù)，只要先按順序排列好，也就是，找到第一個(gè)和不對(duì)應(yīng)的數(shù)就可以了。注意數(shù)組的從開始，而正整數(shù)從開始，所以重寫排列的時(shí)候要注意換成，而就是從開始的數(shù)組中的元素。 Problem Given an unsorted integer array, find the first missing positive integer. Example Given [1,2,0] re...
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 ...
摘要：?jiǎn)未芜x擇最大體積動(dòng)規(guī)經(jīng)典題目，用數(shù)組表示書包空間為的時(shí)候能裝的物品最大容量。注意的空間要給，因?yàn)槲覀円蟮氖堑趥€(gè)值，否則會(huì)拋出。依然是以背包空間為限制條件，所不同的是取的是價(jià)值較大值，而非體積較大值。 Backpack I Problem 單次選擇+最大體積 Given n items with size Ai, an integer m denotes the size of a b...
摘要：做一個(gè)窗口，滿足的左界到右界的距離最小值為所求。循環(huán)的約束條件要注意，不要遺漏不能超過的長(zhǎng)度，但可以等于，因?yàn)榇嬖谒性刂蜑榈臉O端情況。在時(shí)，先更新窗口為當(dāng)前循環(huán)后的最小值，減去最左元素，指針后移。 Problem Given an array of n positive integers and a positive integer s, find the minimal len...
摘要：和唯一的不同是組合中不能存在重復(fù)的元素，因此，在遞歸時(shí)將初始位即可。 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...
閱讀 2735·2021-11-11 17:21
閱讀 627·2021-09-23 11:22
閱讀 3591·2019-08-30 15:55
閱讀 1651·2019-08-29 17:15
閱讀 583·2019-08-29 16:38
閱讀 921·2019-08-26 11:54
閱讀 2517·2019-08-26 11:53
閱讀 2764·2019-08-26 10:31
