## Algorithm Problem: In-Place Merge Sort

The original merge sort version will take O(n) space, and O(nlogn) time.

The O(n) space is the most significant problem of this algorithm. However, there is an O(1) space version, called ‘in-place merge sort’.

## CCI题目：3-6：Stack Sort

1.逐个从st中pop元素，先pop到一个临时变量，如果pop出来的元素比临时变量小，则直接进入buffer，否则，把临时变量顶入buffer，st新pop到临时变量。

2.将buffer中的元素全部倒回st
3.重复1，2两步，直到1中第一种情况不出现为止。

《CCI》上的解法更效率一些（在阶上没有提升），就是在st到buffer中处理的过程中，允许中途将buffer中的元素倒回一部分到st，直到临时变量找到位置，然后继续将st向buffer倒。直到st为空。

Write a program to sort a stack in ascending order. You should not make any assump- tions about how the stack is implemented. The following are the only functions that should be used to write this program: push | pop | peek | isEmpty.

Code

<

pre>

//
// main.cpp
// CCI.3.6.Sort a Stack
//
// Created by Qiu Xiangyu on 12-11-20.
//

# include

using namespace std;
void sortStack(stack &st) {
stack buffer;
bool bubble = true;
int rnd = 1;
while (bubble) {
cout<<“round “<<rnd++<<endl;
bubble = false;
//1.dump numbers from st to buffer and change the order of them
int middle = st.top();
st.pop();
while (st.size()) {
if (middle > st.top()) {
//if st.top is less than the one pop before, then pop to buffer
buffer.push(st.top());
bubble = true;
} else {
//if st.top is ge the one pop before, then push the middle to buffer ,then pop to middle
buffer.push(middle);
middle = st.top();
}
st.pop();
}
buffer.push(middle);
//2.dump buffer to st
while (buffer.size()) {
st.push(buffer.top());
buffer.pop();
}
}
}
int main(int argc, const char * argv[])
{
std::cout << “Hello, World!\n”;
stack st;
srand((unsigned int)clock());
for (int i = 0; i < 100; ++i) {
st.push(rand() % 10);
}
sortStack(st);
while (st.size()) {
cout<<st.top()<<endl;
st.pop();
}
return 0;
}

## LeetCode题目：Sort Colors

cur从0到j扫描，

Sort Colors
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.
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, then 1’s and followed by 2’s.
Could you come up with an one-pass algorithm using only constant space?

```class Solution {
public:
inline void swap(int &a, int &b){
int temp = a;
a = b;
b = temp;
}
void sortColors(int A[], int n) {
if(n <= 1) return;
int i = 0,j = n-1;
int cur = i;
while(cur <= j) {
if(A[cur] == 0) {
if(cur > i) {
swap(A[i++],A[cur]);
} else {
++cur;
++i;
}
} else if (A[cur] == 2) {
if(cur < j)
swap(A[j--],A[cur]);
else
return;
} else
++cur;
}
}
};
```

## LeetCode题目：Merge Sorted Array

Merge Sorted Array
Given two sorted integer arrays A and B, merge B into A as one sorted array.
Note:
You may assume that A has enough space to hold additional elements from B. The number of elements initialized in A and B are m and n respectively.

```class Solution {
public:
void merge(int A[], int m, int B[], int n) {
int last = m + n - 1;
int lasta = m - 1;
int lastb = n - 1;
//select largest to right position
while(lasta >= 0 && lastb >= 0) {
A[last--] = (A[lasta] >= B[lastb] ? A[lasta--] : B[lastb--]);
}
//copy remain numbers in B to A
for(int i = 0 ; i <= lastb; ++i)
A[i] = B[i];
}
};
```

Code rewrite at 2012-12-22

```class Solution {
public:
void merge(int A[], int m, int B[], int n) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
int curi = m + n - 1;
int ia = m - 1;
int ib = n - 1;
while(ia >= 0 && ib >= 0) {
if(A[ia] >= B[ib]) {
A[curi--] = A[ia--];
} else {
A[curi--] = B[ib--];
}
}
while (ib >= 0) {
A[curi--] = B[ib--];
}
}
};
```

Code rewrite at 2012-12-22, The simplest code

```class Solution {
public:
void merge(int A[], int m, int B[], int n) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
int ia = m - 1, ib = n - 1, icur = m + n - 1;
while(ia >= 0 && ib >= 0) {
A[icur--] = A[ia] >= B[ib] ? A[ia--] : B[ib--];
}
while(ib >= 0) {
A[icur--] = B[ib--];
}
}
};
```

## LeetCode题目：Anagrams

1. 题目描述：
Anagrams
Given an array of strings, return all groups of strings that are anagrams.
Note: All inputs will be in lower-case.
2. 思路：
题目是让找出在一个string数组中的所有类似（含有相同字符集，且其中每个字符出现的频率一样）的字符串组。

1. 第一个问题就是如何判断两个字符串anagram。
由于题目中限定了全部是小写，也就是说字符范围是’a’ ~ ‘z’，26个字符，所以可以直接开26个int的数组来统计每个字符串各个字符出现的频率，这样只要两个字符串得到的这种数组相等，就可以认为这两个字符串是类似的。
这个算法的时间复杂度是O(m)。m为字符串长度。
2. 第二个问题就是如何在字符串数组中挑出来类似的字符串。
这个没有想到太好的方法，直接暴力破解吧，不过可以采用一些tricks跳过不必要的计算。
比如先将字符串数组按字符串长度排序，那么长度相等的字符串就落到了一段段连续的地址上，这样就可以很方便地跳过字符串长度不相符的部分。
还可以给第一步得到的int数组进行一个预计算，比如按照fp->abstract += fp->fingerPrint[i] * (i+1);的形式计算一个整数作为预判条件，可以先一步滤掉不可能类似的字符串，从而用单个int相等的判断来避免一部分的数组相等判断。这一步优化使得程序从large测试超时变成了960ms
3. 收获：
1. sort的第三个参数要传递一个静态的函数。
在这个问题上纠结了不少的时间。
另外函数的形式可以是：bool comp(const string &a, const string &b) 或者 bool comp(string a,string b)
2. 容器的resize(n),resize(n,val)函数。

1.

small 8ms, large 超时

```class Solution {
public:
vector getFingerPrint(string &str) {
vector fp(26,0);
for(int i = 0 ; i < str.size(); ++i) {
fp[str[i]-'a'] ++;
}
return fp;
}
static bool AcsByLen(const string &stra, const string &strb) {
return stra.size() < strb.size();
}
vector anagrams(vector &strs) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
vectorresult;
if(strs.size() < 2) {
return result;
}
vector >fps;//finger prints
vector selected(strs.size(),false);
// sort by length
sort(strs.begin(),strs.end(),Solution::AcsByLen);
// calculate the finger prints of strings
for(int i = 0; i < strs.size(); ++i) {
string &str = strs[i];
vector fp = getFingerPrint(str);
fps.push_back(fp);
}
for (int ia = 0 ; ia < strs.size(); ++ia) {
if(selected[ia]) continue;
string &stra = strs[ia];
vector fpa = fps[ia];
for(int ib = ia + 1 ; ib < strs.size(); ++ib) {
if(selected[ib]) continue;
string &strb = strs[ib];
if(strb.size() > stra.size()) {
break;
}
vector fpb = fps[ib];
if (fpb == fpa) {
if(!selected[ia]) {
selected[ia] = true;
result.push_back(stra);
}
selected[ib] = true;
result.push_back(strb);
}
}
}
return result;
}
};
```

2.改进的代码先算了一个整数来作为字符串的抽象指纹，这个整数保证了如果是类似的字符串，这个抽象指纹一定相等；但是抽象指纹相等的字符串不一定是类似的。这个优化使得程序不超时了。
small 4ms, large 960ms

```class Solution {
public:
class FingerPrint {
public:
vector fingerPrint;
int abstract;
};
FingerPrint * getFingerPrint(string &str) {
FingerPrint *fp = new FingerPrint();
fp->fingerPrint.resize(26,0);
for(int i = 0 ; i < str.size(); ++i) {
fp->fingerPrint[str[i]-'a'] ++;
}
fp->abstract = 0;
for(int i = 0 ; i < 26; i ++) {
fp->abstract += fp->fingerPrint[i] * (i+1);
}
return fp;
}
static bool AcsByLen(const string &stra, const string &strb) {
return stra.size() < strb.size();
}
vector anagrams(vector &strs) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
vectorresult;
if(strs.size() < 2) {
return result;
}
vectorfps;//finger prints
vector selected(strs.size(),false);
// sort by length
sort(strs.begin(),strs.end(),Solution::AcsByLen);
// calculate the finger prints of strings
for(int i = 0; i < strs.size(); ++i) {
string &str = strs[i];
FingerPrint &fp = *getFingerPrint(str);
fps.push_back(fp);
}
for (int ia = 0 ; ia < strs.size(); ++ia) {
if(selected[ia]) continue;
string &stra = strs[ia];
FingerPrint &fpa = fps[ia];
for(int ib = ia + 1 ; ib < strs.size(); ++ib) {
if(selected[ib]) continue;
string &strb = strs[ib];
if(strb.size() != stra.size()) {
break;
}
FingerPrint &fpb = fps[ib];
if (fpb.abstract == fpa.abstract
&& fpb.fingerPrint == fpa.fingerPrint) {
if(!selected[ia]) {
selected[ia] = true;
result.push_back(stra);
}
selected[ib] = true;
result.push_back(strb);
}
}
}
return result;
}
};
```

Code rewrite at 2012-12-24, 1048ms pass large set.
Be aware of the usage of static data member in class, notice the last line in this code.
For a ascending sorting, the compare function is just like 'is the first object less than the second one?'.

```class Solution {
public:
static map > g_dict;
static bool compareSign(const string & str0, const string & str1) {
vector & v0 = Solution::g_dict[str0];
vector & v1 = Solution::g_dict[str1];
return v0 < v1;
}
static bool equalSign(const string & str0, const string & str1) {
vector & v0 = Solution::g_dict[str0];
vector & v1 = Solution::g_dict[str1];
return v0 == v1;
}
static bool compare(const string & str0, const string & str1) {
if(str0.size() < str1.size()) {
return true;
} else if(str0.size() > str1.size()) {
return false;
} else {
return Solution::compareSign(str0,str1);
}
}
vector anagrams(vector &strs) {
Solution::g_dict.erase(Solution::g_dict.begin(),Solution::g_dict.end());
for(int i = 0; i < strs.size(); ++i) {
string &str = strs[i];
vector sign(26,0);
for(int j = 0; j < str.size(); ++j) {
++sign[str[j] - 'a'];
}
Solution::g_dict[str] = sign;
}
sort(strs.begin(),strs.end(),Solution::compare);
vector ret;
for (int i = 0; i < strs.size(); ++i) {
string &str = strs[i];
int c = 0;
for (int j = i + 1; j < strs.size(); ++j) {
if (strs[j].size() != str.size()) {
break;
}
if (!Solution::equalSign(strs[j], str)) {
break;
}
if (c == 0) {
ret.push_back(str);
}
ret.push_back(strs[j]);
++c;
}
i += c;
}
return ret;
}
};
map > Solution::g_dict;
```

## iOS开发中对NSArray或者NSMutableArray中的内容排序

``` NSMutableArray *feedsBuffer; //初始化buffer以及填充数据 //....... //排序只需要两句话:已针对数组内对象的publishTime属性(NSDate)排序为例： NSSortDescriptor *sortDescriptor = [[NSSortDescriptor alloc] initWithKey:@"publishTime" ascending:NO]; [feedsBuffer sortUsingDescriptors:[NSArray arrayWithObject:sortDescriptor]]; ```

``` NSArray *sortedArray = [feedsBuffer sortedArrayUsingDescriptors:[NSArray arrayWithObject:sortDescriptor]]; ```

``` [feedsBuffer sortUsingComparator:^NSComparisonResult(id obj1, id obj2) { //返回三者其一:NSOrderedAscending, NSOrderedSame, NSOrderedDescending return NSOrderedSame; }]; ```