摘要:找第一個(gè)缺失的正整數(shù),只要先按順序排列好,也就是,找到第一個(gè)和不對(duì)應(yīng)的數(shù)就可以了。注意數(shù)組的從開始,而正整數(shù)從開始,所以重寫排列的時(shí)候要注意換成,而就是從開始的數(shù)組中的元素。
Problem
Given an unsorted integer array, find the first missing positive integer.
ExampleGiven [1,2,0] return 3,
and [3,4,-1,1] return 2.
找第一個(gè)缺失的正整數(shù),只要先按順序排列好[1, 2, 3, 4, ...],也就是A[i] = i+1,找到第一個(gè)和A[i]不對(duì)應(yīng)的數(shù)i+1就可以了。注意數(shù)組的index從0開始,而正整數(shù)從1開始,所以重寫排列的時(shí)候要注意換成index-1,而index就是從A[0]開始的數(shù)組A[]中的元素。
我們看一個(gè)例子:
[2, 4, -1, 1] --> first for loop --> if (A[i] E (0, A.length) && A[i] != A[A[i]-1]) --> swap(A[i], A[A[i]-1]) --> [4, 2, -1, 1] --> [1, 2, -1, 4] --> second for loop --> A[2] != 3 --> return 2+1 = 3.
之前犯了一個(gè)錯(cuò)誤,因?yàn)榈诙?b>A[i]的值已經(jīng)變了,第三行再代入A[A[i]-1]就會(huì)出錯(cuò):
int temp = A[i]; A[i] = A[A[i]-1]; A[A[i]-1] = temp;Solution
public class Solution { public int firstMissingPositive(int[] A) { int len = A.length; for (int i = 0; i < len; i++) { if (A[i] > 0 && A[i] < len && A[i] != A[A[i]-1]) { int temp = A[A[i]-1]; A[A[i]-1] = A[i]; A[i] = temp; i--; //after the exchange, we need to speculate //and sort that digit again. } } for (int i = 0; i < len; i++) { if (A[i] != i + 1) return i+1; //as array index starts from 0 //and positive starts from 1. } return len + 1; //if the array has 1(A[0]) to len(A[len-1]) //and missed no one, return the len+1. } }
文章版權(quán)歸作者所有,未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為,您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請(qǐng)注明本文地址:http://systransis.cn/yun/65629.html
摘要:題目要求在數(shù)組中找到第一個(gè)漏掉的正整數(shù)。思路一暴力排序后尋找排序后尋找顯然是最快的。這些臨時(shí)變量可以是排除出的量,也可以是有效量。當(dāng)遇到的數(shù)字為有效數(shù)字時(shí),則將該數(shù)字放到對(duì)應(yīng)當(dāng)前起始下標(biāo)其相應(yīng)的位置上。 題目要求 Given an unsorted integer array, find the first missing positive integer. For example,...
Problem Given an unsorted integer array, find the smallest missing positive integer. Example 1: Input: [1,2,0]Output: 3Example 2: Input: [3,4,-1,1]Output: 2Example 3: Input: [7,8,9,11,12]Output: 1Note...
摘要:小鹿題目算法思路桶排序思想。再遍歷數(shù)組,從下標(biāo)開始判斷該下標(biāo)是否存放規(guī)定的數(shù)據(jù),如果不是則該下標(biāo)就是這組數(shù)據(jù)中缺失的最小正整數(shù)。桶排序還可以實(shí)現(xiàn)在一組數(shù)據(jù)中查找重復(fù)的數(shù)據(jù)。 Time:2019/4/6Title: First Missing PositiveDifficulty: DifficultyAuthor: 小鹿 題目:First Missing Positive Give...
摘要:注意,若正數(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 positiv...
摘要:建兩個(gè)新數(shù)組,一個(gè)存數(shù),一個(gè)存。數(shù)組中所有元素初值都是。實(shí)現(xiàn)的過程是,一個(gè)循環(huán)里包含兩個(gè)子循環(huán)。兩個(gè)子循環(huán)的作用分別是,遍歷數(shù)組與相乘找到最小乘積存入再遍歷一次數(shù)組與的乘積,結(jié)果與相同的,就將加,即跳過這個(gè)結(jié)果相同結(jié)果只存一次。 Problem Write a program to find the nth super ugly number. Super ugly numbers a...
閱讀 3334·2021-11-22 12:04
閱讀 2718·2019-08-29 13:49
閱讀 491·2019-08-26 13:45
閱讀 2249·2019-08-26 11:56
閱讀 1007·2019-08-26 11:43
閱讀 601·2019-08-26 10:45
閱讀 1275·2019-08-23 16:48
閱讀 2164·2019-08-23 16:07