448. Find All Numbers Disappeared in an Array
448. Find All Numbers Disappeared in an Array
题目
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]
题目大意
给定一个范围在 1 ≤ a[i] ≤ n ( n = 数组大小 ) 的整型数组,数组中的元素一些出现了两次,另一些只出现一次。找到所有在 [1, n] 范围之间没有出现在数组中的数字。你能在不使用额外空间且时间复杂度为
O(n) 的情况下完成这个任务吗? 你可以假定返回的数组不算在额外空间内。
解题思路
找出 [1,n] 范围内没有出现在数组中的数字。要求不使用额外空间,并且时间复杂度为 O(n)。
要求不能使用额外的空间,那么只能想办法在原有数组上进行修改,并且这个修改是可还原的。时间复杂度也只能允许我们一层循环。只要循环一次能标记出已经出现过的数字,这道题就可以按要
求解答出来。这里笔者的标记方法是把 |nums[i]|-1 索引位置的元素标记为负数。即 nums[| nums[i] |- 1] * -1。这里需要注意的是,nums[i] 需要加绝对值,因为它可能被之前的数置为负数
了,需要还原一下。最后再遍历一次数组,若当前数组元素 nums[i] 为负数,说明我们在数组中存在数字 i+1。把结果输出到最终数组里即可。
代码
package leetcode
全站分卷索引 · 484 卷
- 1关于书的封面
- 2目标读者
- 3第二章 算法专题
- 4Array
- 5Backtracking
- 6Binary Indexed Tree
- 7Bit Manipulation
- 8Breadth First Search
- 9Depth First Search
- 10Dynamic Programming
- 11Hash Table
- 12Linked List
- 13Math
- 14Segment Tree
- 15Sliding Window
- 16Sort
- 17Stack
- 18String
- 19Tree
- 20Two Pointers
- 21Union Find
- 22第三章 一些模板
- 23并查集 UnionFind
- 24第四章 Leetcode 题解
- 251. Two Sum
- 26题目大意
- 27题目大意
- 283. Longest Substring Without Repeating Characters
- 29题目大意
- 304. Median of Two Sorted Arrays
- 31题目大意
- 32代码
- 337. Reverse Integer
- 34解题思路
- 35题目大意
- 3611. Container With Most Water
- 3713. Roman to Integer
- 38题目大意
- 39解题思路
- 4015. 3Sum
- 41代码
- 42题目
- 4317. Letter Combinations of a Phone Number
- 44题目大意
- 4518. 4Sum
- 46题目大意
- 4719. Remove Nth Node From End of List
- 4820. Valid Parentheses
- 49题目大意
- 50题目大意
- 51题目
- 5223. Merge k Sorted Lists
- 5324. Swap Nodes in Pairs
- 54解题思路
- 5525. Reverse Nodes in k-Group
- 5626. Remove Duplicates from Sorted Array
- 57题目大意
- 5827. Remove Element
- 59题目大意
- 6028. Implement strStr()
- 6129. Divide Two Integers
- 62题目大意
- 6330. Substring with Concatenation of All Words
- 6433. Search in Rotated Sorted Array
- 65代码
- 66题目
- 6735. Search Insert Position
- 68题目大意
- 69题目大意
- 7037. Sudoku Solver
- 71题目大意
- 72代码
- 7339. Combination Sum
- 74题目大意
- 7540. Combination Sum II
- 76解题思路
- 7741. First Missing Positive
- 7842. Trapping Rain Water
- 79代码
- 8046. Permutations
- 8147. Permutations II
- 82解题思路
- 8348. Rotate Image
- 84解题思路
- 8549. Group Anagrams
- 86题目大意
- 8750. Pow(x, n)
- 8851. N-Queens
- 89题目大意
- 9052. N-Queens II
- 91题目大意
- 9253. Maximum Subarray
- 9354. Spiral Matrix
- 94题目大意
- 9555. Jump Game
- 9656. Merge Intervals
- 9757. Insert Interval
- 98解题思路
- 9959. Spiral Matrix II
- 10060. Permutation Sequence
- 101题目大意
- 10261. Rotate List
- 103题目大意
- 10462. Unique Paths
- 105题目大意
- 10663. Unique Paths II
- 107解题思路
- 108题目大意
- 10966. Plus One
- 110题目大意
- 11167. Add Binary
- 11269. Sqrt(x)
- 113题目大意
- 114代码
- 11570. Climbing Stairs
- 116题目大意
- 117题目大意
- 11874. Search a 2D Matrix
- 119解题思路
- 120题目大意
- 12176. Minimum Window Substring
- 12277. Combinations
- 123题目大意
- 12478. Subsets
- 12579. Word Search
- 12680. Remove Duplicates from Sorted Array II
- 127题目大意
- 12881. Search in Rotated Sorted Array II
- 129解题思路
- 13082. Remove Duplicates from Sorted List II
- 13183. Remove Duplicates from Sorted List
- 13284. Largest Rectangle in Histogram
- 133题目大意
- 13486. Partition List
- 135代码
- 13688. Merge Sorted Array
- 137题目大意
- 13889. Gray Code
- 139代码
- 14090. Subsets II
- 141解题思路
- 14291. Decode Ways
- 143代码
- 144题目大意
- 14593. Restore IP Addresses
- 14694. Binary Tree Inorder Traversal
- 147题目大意
- 14895. Unique Binary Search Trees II
- 14996. Unique Binary Search Trees
- 150题目大意
- 15198. Validate Binary Search Tree
- 15299. Recover Binary Search Tree
- 153题目大意
- 154100. Same Tree
- 155题目大意
- 156101. Symmetric Tree
- 157102. Binary Tree Level Order Traversal
- 158解题思路
- 159103. Binary Tree Zigzag Level Order Traversal
- 160题目大意
- 161104. Maximum Depth of Binary Tree
- 162题目大意
- 163题目大意
- 164106. Construct Binary Tree from Inorder and Postorder Traversal
- 165解题思路
- 166题目大意
- 167108. Convert Sorted Array to Binary Search Tree
- 168109. Convert Sorted List to Binary Search Tree
- 169解题思路
- 170110. Balanced Binary Tree
- 171题目大意
- 172111. Minimum Depth of Binary Tree
- 173112. Path Sum
- 174代码
- 175题目大意
- 176114. Flatten Binary Tree to Linked List
- 177题目大意
- 178代码
- 179120. Triangle
- 180121. Best Time to Buy and Sell Stock
- 181题目大意
- 182122. Best Time to Buy and Sell Stock II
- 183题目大意
- 184题目
- 185125. Valid Palindrome
- 186题目大意
- 187126. Word Ladder II
- 188题目大意
- 189127. Word Ladder
- 190题目大意
- 191解题思路
- 192128. Longest Consecutive Sequence
- 193代码
- 194129. Sum Root to Leaf Numbers
- 195题目大意
- 196130. Surrounded Regions
- 197题目大意
- 198131. Palindrome Partitioning
- 199136. Single Number
- 200题目大意
- 201题目大意
- 202代码
- 203141. Linked List Cycle
- 204代码
- 205143. Reorder List
- 206代码
- 207144. Binary Tree Preorder Traversal
- 208题目
- 209145. Binary Tree Postorder Traversal
- 210147. Insertion Sort List
- 211题目大意
- 212148. Sort List
- 213150. Evaluate Reverse Polish Notation
- 214题目大意
- 215151. Reverse Words in a String
- 216题目大意
- 217题目
- 218153. Find Minimum in Rotated Sorted Array
- 219154. Find Minimum in Rotated Sorted Array II
- 220解题思路
- 221题目大意
- 222160. Intersection of Two Linked Lists
- 223题目大意
- 224162. Find Peak Element
- 225题目大意
- 226164. Maximum Gap
- 227题目大意
- 228167. Two Sum II - Input array is sorted
- 229题目大意
- 230168. Excel Sheet Column Title
- 231解题思路
- 232题目大意
- 233171. Excel Sheet Column Number
- 234172. Factorial Trailing Zeroes
- 235代码
- 236题目大意
- 237174. Dungeon Game
- 238题目大意
- 239代码
- 240179. Largest Number
- 241题目大意
- 242187. Repeated DNA Sequences
- 243题目大意
- 244190. Reverse Bits
- 245题目大意
- 246题目大意
- 247198. House Robber
- 248解题思路
- 249199. Binary Tree Right Side View
- 250代码
- 251200. Number of Islands
- 252201. Bitwise AND of Numbers Range
- 253题目大意
- 254202. Happy Number
- 255代码
- 256解题思路
- 257题目大意
- 258题目大意
- 259206. Reverse Linked List
- 260207. Course Schedule
- 261题目大意
- 262208. Implement Trie (Prefix Tree)
- 263209. Minimum Size Subarray Sum
- 264210. Course Schedule II
- 265题目大意
- 266211. Add and Search Word - Data structure design
- 267解题思路
- 268212. Word Search II
- 269题目大意
- 270题目大意
- 271215. Kth Largest Element in an Array
- 272代码
- 273题目大意
- 274217. Contains Duplicate
- 275题目大意
- 276题目大意
- 277代码
- 278219. Contains Duplicate II
- 279220. Contains Duplicate III
- 280解题思路
- 281222. Count Complete Tree Nodes
- 282题目大意
- 283223. Rectangle Area
- 284题目大意
- 285题目大意
- 286225. Implement Stack using Queues
- 287题目
- 288226. Invert Binary Tree
- 289题目大意
- 290229. Majority Element II
- 291230. Kth Smallest Element in a BST
- 292题目大意
- 293题目大意
- 294232. Implement Queue using Stacks
- 295题目大意
- 296234. Palindrome Linked List
- 297题目大意
- 298235. Lowest Common Ancestor of a Binary Search Tree
- 299题目大意
- 300代码
- 301题目大意
- 302237. Delete Node in a Linked List
- 303解题思路
- 304题目大意
- 305240. Search a 2D Matrix II
- 306题目大意
- 307242. Valid Anagram
- 308题目大意
- 309257. Binary Tree Paths
- 310258. Add Digits
- 311260. Single Number III
- 312代码
- 313题目大意
- 314题目大意
- 315题目大意
- 316275. H-Index II
- 317题目大意
- 318283. Move Zeroes
- 319287. Find the Duplicate Number
- 320解题思路
- 321290. Word Pattern
- 322题目大意
- 323300. Longest Increasing Subsequence
- 324解题思路
- 325303. Range Sum Query - Immutable
- 326解题思路
- 327306. Additive Number
- 328题目大意
- 329307. Range Sum Query - Mutable
- 330解题思路
- 331309. Best Time to Buy and Sell Stock with Cooldown
- 332题目大意
- 333代码
- 334315. Count of Smaller Numbers After Self
- 335318. Maximum Product of Word Lengths
- 336题目大意
- 337322. Coin Change
- 338题目大意
- 339题目大意
- 340代码
- 341326. Power of Three
- 342题目大意
- 343327. Count of Range Sum
- 344解题思路
- 345代码
- 346328. Odd Even Linked List
- 347题目大意
- 348329. Longest Increasing Path in a Matrix
- 349题目大意
- 350331. Verify Preorder Serialization of a Binary Tree
- 351题目大意
- 352337. House Robber III
- 353题目大意
- 354338. Counting Bits
- 355342. Power of Four
- 356343. Integer Break
- 357代码
- 358题目大意
- 359题目大意
- 360347. Top K Frequent Elements
- 361349. Intersection of Two Arrays
- 362350. Intersection of Two Arrays II
- 363代码
- 364解题思路
- 365357. Count Numbers with Unique Digits
- 366代码
- 367题目大意
- 368题目大意
- 369题目大意
- 370373. Find K Pairs with Smallest Sums
- 371解题思路
- 372378. Kth Smallest Element in a Sorted Matrix
- 373代码
- 374385. Mini Parser
- 375题目大意
- 376386. Lexicographical Numbers
- 377387. First Unique Character in a String
- 378389. Find the Difference
- 379392. Is Subsequence
- 380解题思路
- 381题目
- 382解题思路
- 383394. Decode String
- 384397. Integer Replacement
- 385题目大意
- 386代码
- 387题目大意
- 388代码
- 389401. Binary Watch
- 390题目大意
- 391解题思路
- 392402. Remove K Digits
- 393题目大意
- 394题目大意
- 395题目
- 396代码
- 397题目大意
- 398题目大意
- 399412. Fizz Buzz
- 400题目大意
- 401414. Third Maximum Number
- 402解题思路
- 403题目大意
- 404421. Maximum XOR of Two Numbers in an Array
- 405代码
- 406424. Longest Repeating Character Replacement
- 407题目大意
- 408433. Minimum Genetic Mutation
- 409题目大意
- 410435. Non-overlapping Intervals
- 411题目大意
- 412436. Find Right Interval
- 413题目大意
- 414437. Path Sum III
- 415代码
- 416题目大意
- 417代码
- 418441. Arranging Coins
- 419代码
- 420解题思路
- 421447. Number of Boomerangs
- 422题目大意
- 423448. Find All Numbers Disappeared in an Array
- 424451. Sort Characters By Frequency
- 425题目大意
- 426453. Minimum Moves to Equal Array Elements
- 427题目大意
- 428题目大意
- 429455. Assign Cookies
- 430题目大意
- 431题目大意
- 432457. Circular Array Loop
- 433题目大意
- 434461. Hamming Distance
- 435题目大意
- 436题目大意
- 437470. Implement Rand10() Using Rand7()
- 438题目大意
- 439代码
- 440题目大意
- 441475. Heaters
- 442题目大意
- 443476. Number Complement
- 444477. Total Hamming Distance
- 445解题思路
- 446题目大意
- 447代码
- 448483. Smallest Good Base
- 449题目大意
- 450代码
- 451485. Max Consecutive Ones
- 452代码
- 453解题思路
- 454493. Reverse Pairs
- 455代码
- 456494. Target Sum
- 457代码
- 458496. Next Greater Element I
- 459题目大意
- 460497. Random Point in Non-overlapping Rectangles
- 461解题思路
- 462498. Diagonal Traverse
- 463题目大意
- 464解题思路
- 465500. Keyboard Row
- 466题目大意
- 467题目
- 468507. Perfect Number
- 469题目大意
- 470508. Most Frequent Subtree Sum
- 471509. Fibonacci Number
- 472题目大意
- 473513. Find Bottom Left Tree Value
- 474解题思路
- 475515. Find Largest Value in Each Tree Row
- 476524. Longest Word in Dictionary through Deleting
- 477代码
- 478题目大意
- 479528. Random Pick with Weight
- 480题目大意
- 481代码
- 482529. Minesweeper
- 483题目大意
- 484解题思路