【慢慢學算法】：數組排序（一題多做）

題目描述：

輸入一個數組的值,求出各個值從小到大排序後的次序。

輸入：

輸入有多組資料。

每組輸入的第一個數為數組的長度n(1<=n<=10000),後面的數為數組中的值,以空格分割。

輸出：

各輸入的值按從小到大排列的次序(最後一個數字後面沒有空格)。

樣例輸入：

4
-3 75 12 -3      

樣例輸出：

1 3 2 1      

//單純使用map，利用map中鍵唯一的特性
#include<iostream>
#include<map>
#include<algorithm>
using namespace std;
int A[10010], B[10010];
int main()
{
    int n;
    while(cin >> n)
    {
	map<int,int> m;   
	for(int i = 0; i < n; i++)
	{
	    cin >> A[i];
	    B[i] = A[i];
	}
	sort(B, B+n);
	int index = 0;
	for(int i = 0; i < n; i++)
	{
	    m.insert(pair<int,int>(B[i], index++));
	    if( i!=0 && B[i] == B[i-1])
		index--;
	}
	cout << m.find(A[0])->second+1 ;
	for(int i = 1; i < n; i++)
	    cout << " " << m.find(A[i])->second+1;
	cout << endl;

    }
    
    return 0;
}
           

　　

//利用順序容器vector以及unique算法，效率更高
#include<iostream>
#include<map>
#include<algorithm>
#include<vector>
using namespace std;
int main()
{
    int n;
    while(cin >> n)
    {
	vector<int> A(n);
	map<int,int> m;
	vector<int>::iterator iter = A.begin();
	for(; iter != A.end(); iter++)
	    cin >> *iter;
	vector<int> B(A);
	sort(B.begin(), B.end());
	iter = unique(B.begin(), B.end());
	B.erase(iter,B.end());
	for(int i = 0; i < n; i++)
	{
	    m.insert(pair<int,int>(B[i], i));
	}
	cout << m.find(A[0])->second+1 ;
	for(int i = 1; i < n; i++)
	    cout << " " << m.find(A[i])->second+1;
	cout << endl;
    }
    return 0;
}
           

　　

　list

　　list<int> l

　　插入：push_back尾部，push_front頭部，insert方法前往疊代器位置處插入元素，連結清單自動擴張，疊代器隻能使用++--操作，不能用+n -n，因為元素不是實體相連的。

　　周遊：iterator和reverse_iterator正反周遊

　　删除：pop_front删除連結清單首元素；pop_back()删除連結清單尾部元素；erase（疊代器）删除疊代器位置的元素，注意隻能使用++--到達想删除的位置；remove（key） 删除連結清單中所有key的元素，clear（）清空連結清單。

　　查找：it = find(l.begin(),l.end(),key)

　　排序：l.sort()

 　　删除連續重複元素:l.unique() 【2 8 1 1 1 5 1】 --> 【 2 8 1 5 1】

轉載于:https://www.cnblogs.com/VortexPiggy/archive/2012/07/14/2591189.html