首页 > ACM题库 > 九度OJ > 九度-1167-数组排序[解题代码]
2013
12-13

九度-1167-数组排序[解题代码]

题目来源:2009年北京航空航天大学计算机研究生机试真题

题目描述:

输入一个数组的值,求出各个值从小到大排序后的次序。

输入:

输入有多组数据。
每组输入的第一个数为数组的长度n(1<=n<=10000),后面的数为数组中的值,以空格分割。

输出:

各输入的值按从小到大排列的次序(最后一个数字后面没有空格)。

样例输入:
4
-3 75 12 -3
样例输出:
1 3 2 1

cpp 代码如下:
#include<stdio.h>
#include <algorithm>
#include <stdlib.h>
#include <map>
using namespace std;

int main(){
	int n,*arr,*arr2;
	map<int,int> mymap;
	while(scanf("%d",&n) != EOF){
		arr =(int*)malloc(sizeof(int)*n);
		arr2 = (int*)malloc(sizeof(int)*n);
		for(int i=0;i<n;i++){
		      scanf("%d",&arr[i]);
		      arr2[i] = arr[i];
		}
		sort(arr2,arr2+n);
		int index = 0;
		for(int i=0; i<n; i++){
			mymap.insert(pair<int,int>(arr2[i],index));  //插入数学和对应的  排名
			index ++;
			if( i!=0 && arr2[i]==arr2[i-1])
				index --;
		}
		for(int i=0; i<n; i++){
			if(i==0)
				printf("%d",mymap.find(arr[i])->second+1);
			else
				printf(" %d",mymap.find(arr[i])->second+1);
		}
		printf("\n");
	}
        return 0;
}

/**************************************************************
	Problem: 1167
	User: coder
	Language: C++
	Result: Accepted
	Time:20 ms
	Memory:1416 kb
****************************************************************/

java 代码如下:

import java.io.BufferedInputStream;
import java.util.Arrays;

import java.util.Scanner;


public class Main {
	static int[] arr,arr2;
	static int n;

	public static void main(String[] args) {
		Scanner s = new Scanner(new BufferedInputStream(System.in));
		while (s.hasNextInt()) {
			n = s.nextInt();
			arr = new int[n];
			arr2 = new int[n];
			for (int i = 0; i < n; i++) {
				int temp = s.nextInt();
				arr[i] = temp;
				arr2[i] = temp;
			}
			Arrays.sort(arr2);
			for(int i=0; i<n; i++){
				int index = 0;
				for(int j=0; j<n; j++){
					if(j!=0 && arr2[j]==arr2[j-1])
							index--;
					index++;
					if(arr[i]==arr2[j]){
						if(i==0)
							System.out.print(index);
						else
							System.out.print(" "+index);
						break;
					}
				}
			}
System.out.println();		}
	}
}

/**************************************************************
	Problem: 1167
	User: coder
	Language: Java
	Result: Accepted
	Time:1840 ms
	Memory:43012 kb
****************************************************************/


  1. a是根先忽略掉,递归子树。剩下前缀bejkcfghid和后缀jkebfghicd,分拆的原则的是每个子树前缀和后缀的节点个数是一样的,根节点出现在前缀的第一个,后缀的最后一个。根节点b出现后缀的第四个位置,则第一部分为四个节点,前缀bejk,后缀jkeb,剩下的c出现在后缀的倒数第2个,就划分为cfghi和 fghic,第3部分就为c、c

  2. 其实国内大部分公司对算法都不够重视。特别是中小型公司老板根本都不懂技术,也不懂什么是算法,从而也不要求程序员懂什么算法,做程序从来不考虑性能问题,只要页面能显示出来就是好程序,这是国内的现状,很无奈。

  3. 我还有个问题想请教一下,就是感觉对于新手来说,递归理解起来有些困难,不知有没有什么好的方法或者什么好的建议?

  4. 老实说,这种方法就是穷举,复杂度是2^n,之所以能够AC是应为题目的测试数据有问题,要么数据量很小,要么能够得到k == t,否则即使n = 30,也要很久才能得出结果,本人亲测