資訊專欄INFORMATION COLUMN
摘要：題目鏈接一般這種類型的題要，要么給賦值成不在范圍內(nèi)的數(shù)，要么到對應(yīng)位置。
448. Find All Numbers Disappeared in an Array
題目鏈接：https://leetcode.com/problems...
一般這種類型的題要in place，要么給num[i]賦值成不在范圍內(nèi)的數(shù)，要么swap到對應(yīng)位置。
public class Solution {
public List findDisappearedNumbers(int[] nums) {
List result = new ArrayList();
if(nums.length == 0) return result;
// sign as negative when find a number
for(int i = 0; i < nums.length; i++) {
int index = Math.abs(nums[i]) - 1;
nums[index] = -Math.abs(nums[index]);
}
// find positive number, whose index is not visited
for(int i = 0; i < nums.length; i++) {
if(nums[i] > 0) result.add(i + 1);
}
return result;
}
}
swap的方法見discussion:
https://discuss.leetcode.com/...
public class Solution {
public List findDisappearedNumbers(int[] nums) {
List result = new ArrayList();
if(nums.length == 0) return result;
// swap to correct position
for(int i = 0; i < nums.length; i++) {
while(nums[i] != i + 1 && nums[i] != nums[nums[i] - 1]) {
swap(nums, i, nums[i] - 1);
}
}
// find positive number, whose index is not visited
for(int i = 0; i < nums.length; i++) {
if(nums[i] != i + 1) result.add(i + 1);
}
return result;
}
private void swap(int[] nums, int i, int j) {
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
}
文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請注明本文地址：http://systransis.cn/yun/66657.html
Problem Given an array of integers where 1 ≤ a[i] ≤ n (n = size of array), some elements appear twice and others appear once. Find all the elements of [1, n] inclusive that do not appear in this array...
Problem Given an array of integers where 1 ≤ a[i] ≤ n (n = size of array), some elements appear twice and others appear once. Find all the elements of [1, n] inclusive that do not appear in this array...
摘要：如果這個位置的值為正意味著我們還沒有對這個元素進(jìn)行過操作，我們將這個位置的元素的值取負(fù)。在整個遍歷結(jié)束后，沒有取負(fù)的值的索引，就可以對應(yīng)到?jīng)]有在數(shù)組出現(xiàn)過的值解法 題目詳情 Given an array of integers where 1 ≤ a[i] ≤ n (n = size of array), some elements appear twice and others ap...
摘要：題目要求假設(shè)一個長度為的整數(shù)數(shù)組，數(shù)組中的元素的值位于區(qū)間中。代碼如下但是這個實現(xiàn)違背了的空間復(fù)雜度這里結(jié)果集不視為額外空間。如果當(dāng)前元素?zé)o需進(jìn)行交換，則指針右移一位。無需進(jìn)行的場景是指當(dāng)前元素已經(jīng)出現(xiàn)在目標(biāo)位置上了。 題目要求 Given an array of integers where 1 ≤ a[i] ≤ n (n = size of array), some element...
摘要：題目描述思路先把數(shù)組進(jìn)行升序排序，再進(jìn)行數(shù)組去重，最后循環(huán)比較取得結(jié)果。升序排序可以使用若要降序排列可以則是數(shù)組去重，我使用的中的方法去重，可以參照一行代碼實現(xiàn)數(shù)組去重數(shù)組去重數(shù)組去重方法最優(yōu)解源碼排序去重 題目描述 Given an array of integers where 1 ≤ a[i] ≤ n (n = size of array), some elements appe...
閱讀 1635·2021-10-14 09:43
閱讀 5564·2021-09-07 10:21
閱讀 1290·2019-08-30 15:56
閱讀 2133·2019-08-30 15:53
閱讀 1243·2019-08-30 15:44
閱讀 2020·2019-08-30 15:44
閱讀 1331·2019-08-29 17:24
閱讀 761·2019-08-29 15:19
