美文网首页
排序练习

排序练习

作者: passwd_ | 来源:发表于2017-07-04 16:26 被阅读0次

题目描述:
给你n个整数,请按从大到小的顺序输出其中前m大的数。
输入:
每组测试数据有两行,第一行有两个数n,m(0<n,m<1000000),第二行包含n个各不相同,且都处于区间[-500000,500000]的整数。

输出:
对每组测试数据按从大到小的顺序输出前m大的数。
样例输入:
5 33 -35 92 213 -644

样例输出:
213 92 3

解法1


解法一
#include <iostream>
#include<stdio.h>
#include<string.h>
#include<algorithm>
#define N 1000000
using namespace std;
int a[N];
int main()
{
    int n, m, i, flag = 0;
    while (scanf_s("%d%d", &n, &m) != EOF) {
        for (i = 0;i<n;i++)
            scanf_s("%d", &a[i]);
        sort(a, a + n);
        flag = n - 1;
        printf("%d", a[flag]);
        flag -= 1;
        for (i = m;i>1;i--) {
            printf(" %d", a[flag]);
            flag--;
        }
        cout << endl;
    }
    return 0;
}

解法2


解法二
#include <stdio.h>
#define OFFSET 500000 //偏移量,用于补偿实际数字与数组下标之间偏移
int Hash[1000001]; //偏移量,用于补偿实际数字与数组下标之间偏移
int main() {
    int n, m;
    while (scanf("%d%d", &n, &m) != EOF) {
        for (int i = -500000;i <= 500000;i++) {
            Hash[i + OFFSET] = 0;
        }//初始化,将每个数字都标记为未出现
        for (int i = 1;i <= n;i++) {
            int x;
            scanf("%d", &x);
            Hash[x + OFFSET] = 1; //凡是出现过的数字,该数组元素均被设置成1
        }
        for (int i = 500000;i >= -500000;i--) {  //输出前m个数 
            if (Hash[i + OFFSET] == 1) { //若该数字在输入中出现 
                printf("%d", i); //输出该数字
                m--; //输出一个数字后,m减一,直至m变为0 
                if (m != 0) printf(" "); //注意格式,若m个数未被输出完毕,在输出的 数字后紧跟一个空格
                else {
                    printf("\n"); //若m个数字已经被输出完毕,则在输出的数字后面紧跟 一个换行, 并跳出遍历循环
                        break;
                }
            }
        }
    }
    return 0;
}

解法3


解法三
#include<stdio.h>
#define N 1000000
int array[N];

void quick_sort(int s[], int l, int r)
{
    int i, j, x;
    if (l < r)
    {
        i = l;
        j = r;
        x = s[i];
        while (i < j)
        {
            while (i < j && s[j] > x)
                j--; /* 从右向左找第一个小于x的数 */
            if (i < j)
                s[i++] = s[j];


            while (i < j && s[i] < x)
                i++; /* 从左向右找第一个大于x的数 */
            if (i < j)
                s[j--] = s[i];

        }
        s[i] = x;
        quick_sort(s, l, i - 1); /* 递归调用 */
        quick_sort(s, i + 1, r);
    }
}

int main() {
    int n, m;
    while (scanf_s("%d%d", &n, &m) != EOF) {
        for (int i = 0;i < n;i++) {
            scanf_s("%d", &array[i]);

        }
        quick_sort(array, 0, n - 1);
        int temp = m;
        for (int j = n - 1;j >= n-temp;j--) {
            printf_s("%d", array[j]);
            m--;        
            if (m != 0)
            printf(" ");
            else {
            printf("\n");
            break;
        }       
        }


    }
    return 0;
}

总结:解法三是我自己写的,一次快速排序+反向的for循环。


过程中遇到的错误

输出格式不正确。
解决办法:每次输出数字后m-1,m等于0的时候跳出循环即可。

相关文章

  • day02-11slice_ex

    切片练习 sort排序

  • Rust语言编程实例100题-045

    Rust语言编程实例100题-045 题目:在第39题和42题已经练习过选择排序,插入排序,冒泡排序。今天再来练习...

  • Rust语言编程实例100题-042

    Rust语言编程实例100题-042 题目:在第39题已经练习过插入排序和选择排序。今天来练习下另一种排序——冒泡...

  • 排序练习

    题目描述:给你n个整数,请按从大到小的顺序输出其中前m大的数。输入:每组测试数据有两行,第一行有两个数n,m(0<...

  • iOS + 常用排序算法

    算练习吧参照的原文常用排序算法总结(一)八大排序算法

  • 练习:表格排序

    步骤: 1、先把元素集合类数组转换为数组: 3、按照ary中存储的最新顺序依次的把对应的li添加到页面中: ———...

  • 排序练习(一)

    (1)当代德国著名哲学家海德格尔认为,哲学家应该具有诗人的思维,他说哲学最好的表达方式是诗歌。 (2)陶渊明的《桃...

  • 数据库语言杂记

    MySQL ORDER BY 排序 IF 及 IN 字符串连接函数concat() MySQL练习题:练习题一 ...

  • JAVA目录

    【练习】1 冒泡排序:https://www.jianshu.com/p/36bda9c0578f2 选择排序:h...

  • 排序——选择排序小练习(一)

    版权声明:本文为 Codeagles 原创文章,可以随意转载,但必须在明确位置注明出处!!! 最近在练习写写排序,...

网友评论

      本文标题:排序练习

      本文链接:https://www.haomeiwen.com/subject/jzrxhxtx.html