[Algorithm] 350. Intersection of Two Arrays II
of II ALGORITHM two Arrays intersection 350
2023-09-14 08:59:14 时间
Given two arrays, write a function to compute their intersection.
Example 1:
Input: nums1 = [1,2,2,1], nums2 = [2,2] Output: [2,2]
Example 2:
Input: nums1 = [4,9,5], nums2 = [9,4,9,8,4] Output: [4,9]
Note:
- Each element in the result should appear as many times as it shows in both arrays.
- The result can be in any order.
Not good enough approach
var intersect = function(nums1, nums2) { let r = []; // get larger array const len1 = nums1.length; const len2 = nums2.length; // larger & smaller const larger = len1 > len2 ? nums1: nums2; const smaller = len1 > len2 ? nums2: nums1; // conver larger array to object let hashed = {}; for (let n of larger) { if (n in hashed) { hashed[n]++; } else { hashed[n] = 1; } } // loop over smaller array for (let n of smaller) { if (`${n}` in hashed) { r.push(n); hashed[n] = hashed[n]-1; if (hashed[n] === 0) { delete hashed[n]; } } } return r; };
The reason that code above is not good enough is because, \
1. we use larger array as lookup, this cause more memory usage. -- actually we need to use smaller array as lookup
2. we use 'len1, len2, samller, larger' extra storage, we can actully swap nums1 and nums by one extra function call.
var intersect = function(nums1, nums2) { if (nums1.length > nums2.length) { return intersect(nums2, nums1); } // conver samller array to object let hashed = {}; for (let n of nums2) { if (n in hashed) { hashed[n]++; } else { hashed[n] = 1; } } let r = []; // loop over smaller array for (let n of nums1) { if (hashed[n] > 0) { r.push(n); hashed[n] = hashed[n]-1; } } return r; }
Follow up:
- What if the given array is already sorted? How would you optimize your algorithm?
- What if nums1's size is small compared to nums2's size? Which algorithm is better?
- What if elements of nums2 are stored on disk, and the memory is limited such that you cannot load all elements into the memory at once?
Will write another post for the follow up questions.
相关文章
- git: fatal: Not a git repository (or any of the parent directories): .git
- What Powers Instagram: Hundreds of Instances, Dozens of Technologies(译文,转)
- Json解析异常处理方式(JSONException: Value of type java.lang.String cannot be converted to JSONObject)
- [Javascript] Use an Array of Promises with a For Await Of Loop
- [Algorithm] 350. Intersection of Two Arrays II
- how is component.js of extension project loaded
- Object reference not set to an instance of an object.
- 【Codeforces Round #445 (Div. 2) D】Restoration of string
- ios swift type of expression is ambiguous without more context
- Pape之DL之CNN:2019《A Survey of the Recent Architectures of Deep Convolutional Neural Networks》翻译并解读1~3
- 记录mybatis添加表数据时报出的错误:Could not set property ‘id‘ of ‘class com.xxx.Manager with value ‘xx...xx‘
- 【错误记录】Groovy 函数参数动态类型报错 ( Caught: groovy.lang.MissingMethodException: No signature of method )
- ural 1057 Amount of Degrees(数位DP)
- leetcode 350. Intersection of Two Arrays II
- terminate called after throwing an instance of ‘YAML::TypedBadConversion<int>‘ what(): bad conver
- 【python】解决json.dump(字典)时报错Object of type ‘float32‘ is not JSON serializable
- TypeError: Index of time series must be a pandas DatetimeIndex object.