题目大意
"johnnybravo@mail.com"], ["John", "johnsmith@mail.com", "john_newyork@mail.com"], ["Mary", "mary@mail.com"]]
Output: [["John", 'john00@mail.com', 'john_newyork@mail.com', 'johnsmith@mail.com'],["John", "johnnybravo@mail.com"], ["Mary",
"mary@mail.com"]] Explanation:
The first and third John's are the same person as they have the common email "johnsmith@mail.com".
The second John and Mary are different people as none of their email addresses are used by other accounts.
We could return these lists in any order, for example the answer [['Mary', 'mary@mail.com'], ['John', 'johnnybravo@mail.com'],
['John', 'john00@mail.com', 'john_newyork@mail.com', 'johnsmith@mail.com']] would still be accepted.
Note:
The length of accounts will be in the range [1, 1000].
The length of accounts[i] will be in the range [1, 10].
The length of accounts[i][j] will be in the range [1, 30].
题目大意
给定一个列表 accounts,每个元素 accounts[i] 是一个字符串列表,其中第一个元素 accounts[i][0] 是名称 (name),其余元素是 emails 表示该帐户的邮箱地址。现在,我们想合并这些帐户。如果两个帐户
都有一些共同的邮件地址,则两个帐户必定属于同一个人。请注意,即使两个帐户具有相同的名称,它们也可能属于不同的人,因为人们可能具有相同的名称。一个人最初可以拥有任意数量的帐户,但其所
有帐户都具有相同的名称。合并帐户后,按以下格式返回帐户:每个帐户的第一个元素是名称,其余元素是按顺序排列的邮箱地址。accounts 本身可以以任意顺序返回。
注意:
accounts 的长度将在 [1,1000] 的范围内。
accounts[i] 的长度将在 [1,10] 的范围内。
accounts[i][j] 的长度将在 [1,30] 的范围内。
解题思路
给出一堆账户和对应的邮箱。要求合并同一个人的多个邮箱账户。如果判断是同一个人呢?如果这个人名和所属的其中之一的邮箱是相同的,就判定这是同一个人的邮箱,那么就合并这些邮箱。
这题的解题思路是并查集。不过如果用暴力合并的方法,时间复杂度非常差。优化方法是先把每组数据都进行编号,人编号,每个邮箱都进行编号。这个映射关系用 map 记录起来。如果利用并查
集的 union() 操作,把这些编号都进行合并。最后把人的编号和对应邮箱的编号拼接起来。
这一题有 2 处比较“坑”的是,不需要合并的用户的邮箱列表也是需要排序和去重的,同一个人的所
全站分卷索引 · 462 卷
- 1532. K-diff Pairs in an Array
- 2题目大意
- 3537. Complex Number Multiplication
- 4541. Reverse String II
- 5解题思路
- 6题目大意
- 7代码
- 8547. Friend Circles
- 9解题思路
- 10557. Reverse Words in a String III
- 11代码
- 12题目大意
- 13题目
- 14566. Reshape the Matrix
- 15题目大意
- 16代码
- 17题目大意
- 18572. Subtree of Another Tree
- 19题目大意
- 20575. Distribute Candies
- 21题目大意
- 22解题思路
- 23题目大意
- 24代码
- 25题目大意
- 26628. Maximum Product of Three Numbers
- 27632. Smallest Range Covering Elements from K Lists
- 28代码
- 29633. Sum of Square Numbers
- 30解题思路
- 31题目大意
- 32代码
- 33637. Average of Levels in Binary Tree
- 34638. Shopping Offers
- 35题目大意
- 36解题思路
- 37645. Set Mismatch
- 38题目大意
- 39648. Replace Words
- 40653. Two Sum IV - Input is a BST
- 41题目大意
- 42题目大意
- 43代码
- 44题目大意
- 45662. Maximum Width of Binary Tree
- 46题目大意
- 47代码
- 48668. Kth Smallest Number in Multiplication Table
- 49题目大意
- 50676. Implement Magic Dictionary
- 51题目大意
- 52682. Baseball Game
- 53题目大意
- 54684. Redundant Connection
- 55题目大意
- 56解题思路
- 57题目大意
- 58代码
- 59693. Binary Number with Alternating Bits
- 60题目大意
- 61695. Max Area of Island
- 62题目大意
- 63697. Degree of an Array
- 64代码
- 65题目大意
- 66解题思路
- 67代码
- 68704. Binary Search
- 69代码
- 70题目大意
- 71706. Design HashMap
- 72题目大意
- 73707. Design Linked List
- 74题目大意
- 75710. Random Pick with Blacklist
- 76题目大意
- 77代码
- 78713. Subarray Product Less Than K
- 79代码
- 80题目大意
- 81715. Range Module
- 82题目大意
- 83717. 1-bit and 2-bit Characters
- 84题目大意
- 85题目大意
- 86719. Find K-th Smallest Pair Distance
- 87题目大意
- 88720. Longest Word in Dictionary
- 89题目大意
- 90721. Accounts Merge
- 91题目大意
- 92代码
- 93725. Split Linked List in Parts
- 94题目大意
- 95726. Number of Atoms
- 96题目大意
- 97解题思路
- 98729. My Calendar I
- 99题目大意
- 100解题思路
- 101732. My Calendar III
- 102题目大意
- 103解题思路
- 104733. Flood Fill
- 105解题思路
- 106题目
- 107题目大意
- 108739. Daily Temperatures
- 109744. Find Smallest Letter Greater Than Target
- 110题目大意
- 111745. Prefix and Suffix Search
- 112解题思路
- 113746. Min Cost Climbing Stairs
- 114题目大意
- 115748. Shortest Completing Word
- 116题目大意
- 117753. Cracking the Safe
- 118题目大意
- 119756. Pyramid Transition Matrix
- 120题目大意
- 121代码
- 122题目大意
- 123763. Partition Labels
- 124解题思路
- 125765. Couples Holding Hands
- 126题目大意
- 127代码
- 128题目大意
- 129767. Reorganize String
- 130代码
- 131771. Jewels and Stones
- 132代码
- 133题目大意
- 134代码
- 135781. Rabbits in Forest
- 136题目大意
- 137784. Letter Case Permutation
- 138786. K-th Smallest Prime Fraction
- 139题目大意
- 140793. Preimage Size of Factorial Zeroes Function
- 141解题思路
- 142代码
- 143802. Find Eventual Safe States
- 144解题思路
- 145题目大意
- 146解题思路
- 147811. Subdomain Visit Count
- 148题目
- 149解题思路
- 150812. Largest Triangle Area
- 151题目大意
- 152815. Bus Routes
- 153代码
- 154817. Linked List Components
- 155解题思路
- 156819. Most Common Word
- 157题目大意
- 158826. Most Profit Assigning Work
- 159代码
- 160828. Unique Letter String
- 161代码
- 162832. Flipping an Image
- 163题目大意
- 164题目大意
- 165836. Rectangle Overlap
- 166解题思路
- 167题目大意
- 168839. Similar String Groups
- 169题目大意
- 170841. Keys and Rooms
- 171题目大意
- 172842. Split Array into Fibonacci Sequence
- 173题目大意
- 174844. Backspace String Compare
- 175题目大意
- 176845. Longest Mountain in Array
- 177题目大意
- 178850. Rectangle Area II
- 179题目大意
- 180代码
- 181851. Loud and Rich
- 182题目大意
- 183解题思路
- 184852. Peak Index in a Mountain Array
- 185解题思路
- 186853. Car Fleet
- 187题目大意
- 188856. Score of Parentheses
- 189题目大意
- 190862. Shortest Subarray with Sum at Least K
- 191题目大意
- 192863. All Nodes Distance K in Binary Tree
- 193题目大意
- 194代码
- 195864. Shortest Path to Get All Keys
- 196解题思路
- 197867. Transpose Matrix
- 198872. Leaf-Similar Trees
- 199题目大意
- 200代码
- 201题目大意
- 202876. Middle of the Linked List
- 203题目大意
- 204878. Nth Magical Number
- 205题目大意
- 206880. Decoded String at Index
- 207题目大意
- 208881. Boats to Save People
- 209解题思路
- 210题目大意
- 211885. Spiral Matrix III
- 212题目大意
- 213887. Super Egg Drop
- 214题目大意
- 215代码
- 216题目
- 217解题思路
- 218891. Sum of Subsequence Widths
- 219代码
- 220题目大意
- 221895. Maximum Frequency Stack
- 222题目大意
- 223解题思路
- 224896. Monotonic Array
- 225题目大意
- 226897. Increasing Order Search Tree
- 227解题思路
- 228898. Bitwise ORs of Subarrays
- 229题目大意
- 230代码
- 231901. Online Stock Span
- 232题目大意
- 233904. Fruit Into Baskets
- 234题目大意
- 235907. Sum of Subarray Minimums
- 236代码
- 237911. Online Election
- 238解题思路
- 239914. X of a Kind in a Deck of Cards
- 240题目大意
- 241918. Maximum Sum Circular Subarray
- 242题目大意
- 243代码
- 244题目大意
- 245代码
- 246921. Minimum Add to Make Parentheses Valid
- 247题目大意
- 248题目大意
- 249题目
- 250924. Minimize Malware Spread
- 251题目大意
- 252解题思路
- 253925. Long Pressed Name
- 254题目大意
- 255927. Three Equal Parts
- 256题目大意
- 257928. Minimize Malware Spread II
- 258题目大意
- 259解题思路
- 260930. Binary Subarrays With Sum
- 261代码
- 262题目大意
- 263942. DI String Match
- 264代码
- 265题目大意
- 266题目
- 267代码
- 268题目大意
- 269952. Largest Component Size by Common Factor
- 270题目大意
- 271代码
- 272953. Verifying an Alien Dictionary
- 273题目大意
- 274959. Regions Cut By Slashes
- 275题目大意
- 276代码
- 277961. N-Repeated Element in Size 2N Array
- 278代码
- 279题目大意
- 280代码
- 281969. Pancake Sorting
- 282题目大意
- 283970. Powerful Integers
- 284题目大意
- 285973. K Closest Points to Origin
- 286题目大意
- 287976. Largest Perimeter Triangle
- 288题目大意
- 289题目大意
- 290978. Longest Turbulent Subarray
- 291题目大意
- 292979. Distribute Coins in Binary Tree
- 293题目大意
- 294代码
- 295980. Unique Paths III
- 296题目大意
- 297981. Time Based Key-Value Store
- 298题目大意
- 299解题思路
- 300984. String Without AAA or BBB
- 301题目大意
- 302985. Sum of Even Numbers After Queries
- 303题目大意
- 304986. Interval List Intersections
- 305代码
- 306题目大意
- 307解题思路
- 308题目
- 309代码
- 310993. Cousins in Binary Tree
- 311题目大意
- 312解题思路
- 313995. Minimum Number of K Consecutive Bit Flips
- 314题目大意
- 315代码
- 316996. Number of Squareful Arrays
- 317代码
- 318999. Available Captures for Rook
- 319题目大意
- 320解题思路
- 3211002. Find Common Characters
- 3221003. Check If Word Is Valid After Substitutions
- 323题目大意
- 324解题思路
- 3251004. Max Consecutive Ones III
- 3261005. Maximize Sum Of Array After K Negations
- 327题目大意
- 3281011. Capacity To Ship Packages Within D Days
- 329题目大意
- 3301017. Convert to Base -2
- 331解题思路
- 332题目大意
- 3331020. Number of Enclaves
- 334题目大意
- 3351021. Remove Outermost Parentheses
- 336题目大意
- 337代码
- 3381025. Divisor Game
- 339代码
- 340题目大意
- 341解题思路
- 342题目大意
- 343解题思路
- 3441030. Matrix Cells in Distance Order
- 345题目大意
- 346代码
- 347题目大意
- 348题目大意
- 349代码
- 3501047. Remove All Adjacent Duplicates In String
- 351题目大意
- 3521049. Last Stone Weight II
- 353代码
- 354题目大意
- 3551052. Grumpy Bookstore Owner
- 356解题思路
- 3571054. Distant Barcodes
- 358题目大意
- 3591073. Adding Two Negabinary Numbers
- 360题目大意
- 361代码
- 3621074. Number of Submatrices That Sum to Target
- 363解题思路
- 3641078. Occurrences After Bigram
- 365解题思路
- 366题目大意
- 3671089. Duplicate Zeros
- 3681093. Statistics from a Large Sample
- 369题目大意
- 3701105. Filling Bookcase Shelves
- 371题目大意
- 3721108. Defanging an IP Address
- 373代码
- 374题目大意
- 3751111. Maximum Nesting Depth of Two Valid Parentheses Strings
- 376题目大意
- 377代码
- 3781122. Relative Sort Array
- 379解题思路
- 3801123. Lowest Common Ancestor of Deepest Leaves
- 381题目大意
- 3821128. Number of Equivalent Domino Pairs
- 383解题思路
- 384题目大意
- 3851145. Binary Tree Coloring Game
- 386题目大意
- 387解题思路
- 3881154. Day of the Year
- 389题目大意
- 390题目
- 391解题思路
- 392代码
- 3931160. Find Words That Can Be Formed by Characters
- 394解题思路
- 395题目大意
- 396代码
- 397题目大意
- 3981175. Prime Arrangements
- 399题目大意
- 4001184. Distance Between Bus Stops
- 401题目大意
- 402解题思路
- 403题目大意
- 404题目
- 405代码
- 406题目大意
- 4071201. Ugly Number III
- 408解题思路
- 409题目大意
- 410解题思路
- 4111207. Unique Number of Occurrences
- 4121208. Get Equal Substrings Within Budget
- 413题目大意
- 4141217. Play with Chips
- 415题目大意
- 416题目
- 417代码
- 418题目大意
- 419解题思路
- 420题目大意
- 421代码
- 422题目大意
- 4231252. Cells with Odd Values in a Matrix
- 424题目大意
- 425解题思路
- 4261254. Number of Closed Islands
- 427题目大意
- 4281260. Shift 2D Grid
- 429题目大意
- 430代码
- 431题目大意
- 432题目大意
- 433代码
- 4341281. Subtract the Product and Sum of Digits of an Integer
- 4351283. Find the Smallest Divisor Given a Threshold
- 436题目大意
- 4371287. Element Appearing More Than 25% In Sorted Array
- 4381290. Convert Binary Number in a Linked List to Integer
- 439题目大意
- 440题目大意
- 4411299. Replace Elements with Greatest Element on Right Side
- 4421300. Sum of Mutated Array Closest to Target
- 443解题思路
- 4441302. Deepest Leaves Sum
- 4451304. Find N Unique Integers Sum up to Zero
- 446解题思路
- 447题目大意
- 448解题思路
- 449题目大意
- 4501313. Decompress Run-Length Encoded List
- 451解题思路
- 452题目大意
- 4531380. Lucky Numbers in a Matrix
- 454题目大意
- 4551385. Find the Distance Value Between Two Arrays
- 456题目大意
- 4571389. Create Target Array in the Given Order
- 458题目大意
- 459题目大意
- 460题目大意
- 4611470. Shuffle the Array
- 462解题思路