CCI题目:3-6:Stack Sort

其实是冒泡排序,两个stack来回倒腾。
代码展示的是比较直观的算法,对st排序,用另一个栈buffer作为辅助空间,那么:

1.逐个从st中pop元素,先pop到一个临时变量,如果pop出来的元素比临时变量小,则直接进入buffer,否则,把临时变量顶入buffer,st新pop到临时变量。
最后把临时变量push进buffer。
2.将buffer中的元素全部倒回st
3.重复1,2两步,直到1中第一种情况不出现为止。

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

此外,想到一个O(nlogn)的方法,就是,既然要用到额外最多s.size()的空间,还不如建一个最大值堆,把从stackpop出来的内容放到堆里面,然后将最大值逐个push回去。O(n logn),比参考答案快。



题目
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.
注:是允许用额外的Stack作为辅助空间的。



Code

<

pre>

//
// main.cpp
// CCI.3.6.Sort a Stack
//
// Created by Qiu Xiangyu on 12-11-20.
// Copyright (c) 2012年 Qiu Xiangyu. All rights reserved.
//

include

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

已经有点浆糊了,其实很简单,用i记录0应该放的位置,j记录2应该放的位置。
cur从0到j扫描,
遇到0,放在i位置,i后移;
遇到2,放在j位置,j前移;
遇到1,cur后移。
扫描一遍得到排好序的数组。
时间O(n)且一次扫描,空间O(1),满足要求。
这么做的前提是,拿到一个值,就知道它应该放在哪儿。(这点和快排的根据pivot交换元素有点像)



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



代码:16ms过大集合

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.



从大到小,选取两个数组末端大的那个数,放到A的末尾即可。



代码:24ms过大集合,时间复杂度是O(n)

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--];
        }
    }
};

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

在iOS开发中,排序是很简单的事情:


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

假如feedsBuffer是NSArray,那么有一个方法是

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

如果排序的依据比较复杂,那么可以使用Block进行大小判断自定义:

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