資訊專欄INFORMATION COLUMN
摘要：題目要求假設(shè)一個(gè)長(zhǎng)度為的整數(shù)數(shù)組，數(shù)組中的元素的值位于區(qū)間中。代碼如下但是這個(gè)實(shí)現(xiàn)違背了的空間復(fù)雜度這里結(jié)果集不視為額外空間。如果當(dāng)前元素?zé)o需進(jìn)行交換，則指針右移一位。無(wú)需進(jìn)行的場(chǎng)景是指當(dāng)前元素已經(jīng)出現(xiàn)在目標(biāo)位置上了。
題目要求
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. Could you do it without extra space and in O(n) runtime? You may assume the returned list does not count as extra space. Example: Input: [4,3,2,7,8,2,3,1] Output: [5,6]
假設(shè)一個(gè)長(zhǎng)度為n的整數(shù)數(shù)組，數(shù)組中的元素的值位于[1,n]區(qū)間中。問(wèn)，該數(shù)組中有哪些[1,n]區(qū)間中的整數(shù)沒有出現(xiàn)？
思路和代碼首先可以想到用另一個(gè)臨時(shí)數(shù)組來(lái)記錄每個(gè)元素出現(xiàn)的次數(shù)，則出現(xiàn)次數(shù)為零次的元素在數(shù)組中沒有出現(xiàn)。代碼如下：
public ListfindDisappearedNumbers(int[] nums) { int[] temp = new int[nums.length + 1]; for (int i = 0; i < nums.length; i++) { temp[nums[i]]++; } List result = new ArrayList<>(); for (int i = 1; i < temp.length; i++) { if (temp[i] == 0) { result.add(i); } } return result; }
但是這個(gè)實(shí)現(xiàn)違背了O(1)的空間復(fù)雜度（這里結(jié)果集不視為額外空間）。因此如何才能避免使用臨時(shí)數(shù)組呢？其實(shí)我們可以利用原數(shù)組中元素相互調(diào)換的方式，將其轉(zhuǎn)化為一個(gè)新的有序的數(shù)組。即從最左邊開始，每遇到一個(gè)元素，就將其防止到元素的目標(biāo)位置上，如在第0位上遇到元素i，則將位置i-1上的元素和位置0上的元素進(jìn)行交換，并在此判斷新的元素是否需要交換。如果當(dāng)前元素?zé)o需進(jìn)行交換，則指針右移一位。無(wú)需進(jìn)行的場(chǎng)景是指當(dāng)前元素已經(jīng)出現(xiàn)在目標(biāo)位置上了。
public ListfindDisappearedNumbers(int[] nums) { int index = 0; while(index < nums.length) { if(nums[index] == nums[nums[index]-1]) { nums[nums[index]-1] = nums[index]; index++; }else{ int tmp = nums[index]; nums[index] = nums[tmp-1]; nums[tmp-1] = tmp; } } List result = new ArrayList (); for(int i = 0 ; i < nums.length ; i++) { if(nums[i] != i+1) { result.add(i+1); } } return result; }
文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請(qǐng)注明本文地址：http://specialneedsforspecialkids.com/yun/74414.html
摘要：如果這個(gè)位置的值為正意味著我們還沒有對(duì)這個(gè)元素進(jìn)行過(guò)操作，我們將這個(gè)位置的元素的值取負(fù)。在整個(gè)遍歷結(jié)束后，沒有取負(fù)的值的索引，就可以對(duì)應(yīng)到?jīng)]有在數(shù)組出現(xiàn)過(guò)的值解法 題目詳情 Given an array of integers where 1 ≤ a[i] ≤ n (n = size of array), some elements appear twice and others ap...
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...
摘要：題目鏈接一般這種類型的題要，要么給賦值成不在范圍內(nèi)的數(shù)，要么到對(duì)應(yīng)位置。 448. Find All Numbers Disappeared in an Array 題目鏈接：https://leetcode.com/problems... 一般這種類型的題要in place，要么給num[i]賦值成不在范圍內(nèi)的數(shù)，要么swap到對(duì)應(yīng)位置。 public class Solution ...
摘要：題目鏈接題目分析給定一個(gè)到的數(shù)組，返回其中缺失的數(shù)字。思路用得出到的數(shù)字，再用和給定的數(shù)組計(jì)算差集。最終代碼若覺得本文章對(duì)你有用，歡迎用愛發(fā)電資助。 D79 448. Find All Numbers Disappeared in an Array 題目鏈接 448. Find All Numbers Disappeared in an Array 題目分析 給定一個(gè)1到n的數(shù)組，返回...
閱讀 3477·2021-09-06 15:13
閱讀 1527·2021-09-02 10:19
閱讀 2473·2019-08-30 15:52
閱讀 918·2019-08-29 15:25
閱讀 1565·2019-08-26 18:36
閱讀 495·2019-08-26 13:23
閱讀 1331·2019-08-26 10:46
閱讀 3498·2019-08-26 10:41
