美文网首页
A1045 快速排序 (25分)

A1045 快速排序 (25分)

作者: km15 | 来源:发表于2020-02-07 17:58 被阅读0次

/*
题意:
1、找主元,就是左边比他小,右边比它都打就是主元了

解题:
1、答案说思路一样,怎么个一样法。我需要判断每一个数,左边是否都小于我,右边是否比我大,two points是根据两边i和j的规律,这算是打表,仔细体会B1040的打表
2、

learn && wrong:
1、左边记录最大值,右边记录最小值的写法不错
*/

#include <iostream>
#include <algorithm>
using namespace std; 

const int maxn = 100010;
const int INF = 0x3fffffff; //一个很大的数

//a为序列,leftmax和rightmin分别为每一位左边最大的数和右边最小的数
int a[maxn],leftmax[maxn],rightmin[maxn];

//ans记录所有主元,Num为主元个数

int ans[maxn],num = 0; 
int main(int argc, char** argv) {
    int n;
    cin>>n;//序列元素个数
    for(int i = 0;i < n;++i){
        scanf("%d",&a[i]);
    } 
    
    leftmax[0] = 0; //a[0]左边没有比它更大的数
    for(int i = 1;i < n;++i){
        leftmax[i] = max(leftmax[i - 1],a[i - 1]);  //由a[i - 1]推得i 
    } 
    
    rightmin[n - 1] = INF; //a[n - 1]右边没有比它更小的数 
    for(int i = n - 2;i >= 0;--i){
        rightmin[i] = min(rightmin[i + 1], a[i + 1]);  //由a[i + 1]推得a[i] 
    }
    
    for(int i = 0;i < n;++i){
        //左边所有数比它小,右边所有数比他大
        if(leftmax[i] < a[i] && rightmin[i] > a[i]){
            ans[num++] = a[i]; //记录主元 
        } 
    } 
    
    printf("%d\n",num); //主元个数
    for(int i = 0;i < num;++i){
        printf("%d", ans[i]);
        if(i != (num -1)) printf(" ");
    } 
    printf("\n");
    return 0;
}

相关文章

  • A1045 快速排序 (25分)

    /*题意:1、找主元,就是左边比他小,右边比它都打就是主元了 解题:1、答案说思路一样,怎么个一样法。我需要判断每...

  • 七大排序算法之快速排序

    七大排序算法之快速排序 @(算法笔记)[排序算法, 快速排序, C++实现] [TOC] 快速排序的介绍: 快速排...

  • 面试准备--排序

    堆排序 快速排序(simple) 快速排序(regular) 归并排序 Shell排序 插入排序 选择排序 冒泡排序

  • 排序

    插入排序 选择排序 冒泡排序 归并排序 快速排序* 三路快速排序

  • 算法笔记01-排序#2

    快速排序敢叫快速排序,那它一定得快。 快速排序 概述 快速排序也是分治排序的典型,它快,而且是原地排序。不过,要防...

  • PHP 实现快速排序

    导语 这篇了解下快速排序。 快速排序 快速排序(英语:Quicksort),又称划分交换排序(partition-...

  • 快速排序的Python实现

    目录 快速排序的介绍 快速排序的Python实现 快速排序的介绍 快速排序(quick sort)的采用了分治的策...

  • 数据结构与算法 快速排序

    起因:快速排序,又称分区交换排序,简称快排,之前没有了解过,抽空学习一下。 快速排序 1 快速排序 快速排序的定义...

  • 数组-快速排序

    采用快速方式对数组进行排序 快速排序百科:快速排序(Quicksort)是对冒泡排序算法的一种改进.快速排序是通过...

  • OC数据结构&算法

    更多整理资料尽在?一平米小站 目录 选择排序 冒泡排序 插入排序 快速排序 双路快速排序 三路快速排序 堆排序 选...

网友评论

      本文标题:A1045 快速排序 (25分)

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