Description

Given two arrays, write a function to compute their intersection.

Each element in the result should appear as many times as it shows in both arrays.The result can be in any order.

Example

Example1

Input: 
nums1 = [1, 2, 2, 1], nums2 = [2, 2]
Output: 
[2, 2]

Example2

Input: 
nums1 = [1, 1, 2], nums2 = [1]
Output: 
[1]

Challenge

• What if the given array is already sorted? How would you optimize your algorithm?
• What if nums1’s size is small compared to num2’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?

Leetcode - 349 Intersection of Two Arrays

Description

Given two arrays, write a function to compute their intersection.

Each element in the result must be unique.The order of the results needs to be ascending

Example

Example 1:

Input: nums1 = [1, 2, 2, 1], nums2 = [2, 2], 
Output: [2].

Example 2:

Input: nums1 = [1, 2], nums2 = [2], 
Output: [2].

Description

Merge two sorted (ascending) lists of interval and return it as a new sorted list. The new sorted list should be made by splicing together the intervals of the two lists and sorted in ascending order.

The intervals in the given list do not overlap.The intervals in different lists may overlap.

Example

Example1

Input: list1 = [(1,2),(3,4)] and list2 = [(2,3),(5,6)]
Output: [(1,4),(5,6)]
Explanation:
(1,2),(2,3),(3,4) --> (1,4)
(5,6) --> (5,6)

Example2

Input: list1 = [(1,2),(3,4)] and list2 = [(4,5),(6,7)]
Output: [(1,2),(3,5),(6,7)]
Explanation:
(1,2) --> (1,2)
(3,4),(4,5) --> (3,5)
(6,7) --> (6,7)

Description

Merge two given sorted ascending integer array A and B into a new sorted integer array.

Example

Example 1:

Input:  A=[1], B=[1]
Output: [1,1]	
Explanation:  return array merged.

Example 2:

Input:  A=[1,2,3,4], B=[2,4,5,6]
Output: [1,2,2,3,4,4,5,6]	
Explanation: return array merged.

Challenge

How can you optimize your algorithm if one array is very large and the other is very small?

Description

Given two sorted integer arrays A and B, merge B into A as one sorted array.

You may assume that A has enough space (size that is greater or equal to m + n) to hold additional elements from B. The number of elements initialized in A and B are m and n respectively.

Example

Example 1:

Input：[1, 2, 3] 3  [4,5]  2
Output：[1,2,3,4,5]
Explanation:
After merge, A will be filled as [1, 2, 3, 4, 5]

Example 2:

Input：[1,2,5] 3 [3,4] 2
Output：[1,2,3,4,5]
Explanation:
After merge, A will be filled as [1, 2, 3, 4, 5]

Description

Given an integer array, sort it in ascending order in place. Use quick sort, merge sort, heap sort or any O(nlogn) algorithm.

Example

Example1:

Input: [3, 2, 1, 4, 5], 
Output: [1, 2, 3, 4, 5].

Example2:

Input: [2, 3, 1], 
Output: [1, 2, 3].

Description

Given an integer array, sort it in ascending order. Use selection sort, bubble sort, insertion sort or any O(n2) algorithm.

Example

Example 1:
	Input:  [3, 2, 1, 4, 5]
	Output: [1, 2, 3, 4, 5]
	
	Explanation: 
	return the sorted array.

Example 2:
	Input:  [1, 1, 2, 1, 1]
	Output: [1, 1, 1, 1, 2]
	
	Explanation: 
	return the sorted array.

Problem

Given a sorted array nums, remove the duplicates in-place such that duplicates appeared at most twice and return the new length.

Do not allocate extra space for another array, you must do this by modifying the input array in-place with O(1) extra memory.

Example 1:

Given nums = [1,1,1,2,2,3],

Your function should return length = 5, with the first five elements of nums being 1, 1, 2, 2 and 3 respectively.

It doesn't matter what you leave beyond the returned length.

Example 2:

Given nums = [0,0,1,1,1,1,2,3,3],

Your function should return length = 7, with the first seven elements of nums being modified to 0, 0, 1, 1, 2, 3 and 3 respectively.

It doesn't matter what values are set beyond the returned length.

Clarification:

Confused why the returned value is an integer but your answer is an array?

Note that the input array is passed in by reference, which means modification to the input array will be known to the caller as well.

Internally you can think of this:

// nums is passed in by reference. (i.e., without making a copy)
int len = removeDuplicates(nums);

// any modification to nums in your function would be known by the caller.
// using the length returned by your function, it prints the first len elements.
for (int i = 0; i < len; i++) {
    print(nums[i]);
}