It's never too late to learn to be a master
Intersection of Two unsorted Arrays
Given two arrays, write a function to compute their intersection.
Example:
Given nums1 = [1, 2, 2, 1], nums2 = [2, 2], return [2].
Note:
Analysis
Since the two arrays are unsorted, we can use HashSet to solve the problem easily.
We can also solve the problem by first sorting the two arrays, and using the algorithm of finding intersection of two sorted arrays.
[Read More...]Quicksort is one of the most famous sort algorithms because of its average good performance. Because of its importance and popularity, it is usually asked in technique interviews. It is also important to master QuickSort as its partitioning technique can also be used to find the Kth largest or smallest element of an array in O(n) time with O(1) space complexity.
How quickSort algorithm works
Given an array A[s … e], a pivot is chosen to rearrange the array into two parts: ALeft and Aright. All the elements in ALeft are less than or equal to the pivot,
[Read More...]Given an array with n objects colored red, white or blue, sort them so that objects of the same color are adjacent, with the colors in the order red, white and blue.
Here, we will use the integers 0, 1, and 2 to represent the color red, white, and blue respectively.
Note:
You are not suppose to use the library’s sort function for this problem.
Follow up:
A rather straight forward solution is a two-pass algorithm using counting sort.
First, iterate the array counting number of 0’s, 1’s, and 2’s, then overwrite array with total number of 0’s,
Selection sort is one of the simplest sorting algorithms. This tutorial described how to implement selection sort algorithm in python.
The basic idea of selection sort is that it repeatedly select the smallest item in list A[i+1:], and exchange it with the item at A[i].
It works as follows:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 |
def sort(A): i = 0 j = i + 1 #find the smallest item in A[i+1:] min = i while i < len(A): print 'i= {0}, A is {1}'.format(i, A) j = i + 1 while j < len(A): if A[j] < A[i]: min = j j += 1 swap(A, i, min) print 'After {0}th round, A is {1}'.format(i, A) i += 1 def swap(A, i, j): temp = A[i] A[i] = A[j] A[j] = temp A = [2,4,6,1,3,5,7] sort(A) |
Rss Feeds