CareerCup Chapter 9 Sorting and Searching - hrhguanli - 博客园
9.1 You are given two sorted arrays, A and B, and A has a large enough buffer at the end to hold B. Write a method to merge B into A in sorted order.
A has enough buffer at the end to hold B, we can merge two arrays from end to start index, like merge two arrays in merge sort algorithm.
void mergeTwoArray(int A[],int m,int B[],int n){
int k=m+n-1;
m--;n--;
while(m>=0&&n>=0){
if(A[m]>=B[n])A[k--]=A[m--];
else A[k--]=B[n--];
}
while(m>=0)A[k--]=A[m--];
while(n>=0)A[k--]=B[n--];
}
9.2 Write a method to sort an array of strings so that all the anagrams are next to each other.
Based on basic sort function, we define a cmp function to decide how to sort. Here, we compare theirs anagrams' state.
int cmp(string s1,string s2){
sort(s1.begin(),s1.end());
sort(s2.begin(),s2.end());
if(s1<s2)return 1;
else return 0;
}
void sortStrings(vector<string> &strs){
sort(strs.begin(),strs.end(),cmp);
}
**9.3 Given a sorted array of n integers that has been rotated an unknown number of times, give an O(log n) algorithm that finds an element in the array. You may assume that the array was originally sorted in increasing order.
EXAMPLE:
Input: find 5 in array (15 16 19 20 25 1 3 4 5 7 10 14)
Output: 8 (the index of 5 in the array)
like binary search, we declare left/mid/right variables to represent current array part, because the array is rotated, we will have 8 states as following: k is the goal data.
k<a[mid],k<a[left],k<a[right], in this condition, right=mid-1 || left=mid+1, for we cannot make sure which part including rotated part.
Read full article from CareerCup Chapter 9 Sorting and Searching - hrhguanli - 博客园
No comments:
Post a Comment