美文网首页
算法很美--查找与排序

算法很美--查找与排序

作者: Archer_ll | 来源:发表于2019-03-23 15:27 被阅读0次

题目1 : Exam13_Median
时间限制:5000ms
单点时限:1000ms
内存限制:256MB

描述

给定一个正整数数组,请求出自第一个元素开始到每个元素为终点的中位数。
输入

第一行:N(1<N<=1000),代表数组的长度
第二行:N个整数,作为数组的元素,空格分开
输出

N个整数,空格隔开;第一位是数组第一个元素,第二位是前两个元素的上中位数……
样例输入

5
4 6 9 4 5

样例输出

4 4 6 4 5

AC代码

#include<stdio.h>
/// 化问题为求单个数组的中位数
void px(int*a,int i)    //  地址传递,可节约运行时间
{
    int j,jj;
    for(j=i;j>0;j--)
        for(jj=0;jj<j;jj++)
        {
            if(a[jj]>a[jj+1])   //  交换两个数
            {
                a[jj]+=a[jj+1];
                a[jj+1]=a[jj]-a[jj+1];
                a[jj]=a[jj]-a[jj+1];
            }
        }
    printf("%d ",a[i/2]);
}
main()
{
    int n,i;
    scanf("%d",&n);
    int a[n]; 
    for(i=0;i<n;i++)
        scanf("%d",&a[i]);
    for(i=0;i<n;i++)
    {
        px(a,i);
    }
    return 0;
} 

时间限制:5000ms
单点时限:1000ms
内存限制:256MB

描述

数组小和的定义如下:

例如:数组s = [1, 3, 5, 2, 4, 6],在s[1]的左边小于或等于s[1]的数的和为1,在s[2]的左边小于或等于s[2]的数有1和3,求和为4,……,将所有位置的左边比它小或者等于的数的和相加起来就是真个数组的小和。

给定一个数组,输出数组的小和。
输入

第一行:N(1<N<=100000),代表数组的长度
第二行:N个整数(<=100),作为数组的元素,空格分开
输出

数组的小和
样例输入

5
58 74 14 39 15

样例输出

86

AC代码 ---Java

//计算数组的小和
import java.util.*;

public class Main{
    
    //方法二(归并排序),时间复杂度为O(NlogN),额外的空间复杂度为O(N)
    public static int GetMinArrSum2(int[]arr)
    {
        if(arr==null||arr.length==0)
        {
            return 0;
        }
        return func(arr,0,arr.length-1);

    }
  //运用递归函数实现
    public static int func(int[]arr,int l,int r)
    {
        //递归的出口
        if(l==r)
        {
            return 0;
        }
        int mid=(l+r)/2; //中间位置的数
        return func(arr,l,mid)+func(arr,mid+1,r)+merge(arr,l,mid,r);
    }   
  //归并排序的具体实现
    public static int merge(int[]arr,int l,int mid,int r)
    {
        int[]h=new int[r-l+1]; //开辟O(N)的空间
        int hi=0;
        int i=l;
        int j=mid+1;
        int smallSum=0;
        while(i<=mid&&j<=r)
        {
            if(arr[i]<=arr[j])
            {
                smallSum+=arr[i]*(r-j+1);
                h[hi++]=arr[i++];
            }else
            {
                h[hi++]=arr[j++];
            }
        }
        for(;(j<r+1)||(i<mid+1);j++,i++)
        {
            h[hi++]=i>mid?arr[j]:arr[i];
        }

        //对原数组的重新赋值
        for(int k=0;k!=h.length;k++)
        {
            arr[l++]=h[k];
        }    
        return smallSum;
    }

  //打印数组的内容
    public static void PrintArr(int[]arr)
    {
        for(int i=0;i<arr.length;i++)
        {
            System.out.print(arr[i]+" ");
        }
        System.out.println();
    }
    public static void main(String[]args)
    {
        //System.out.println("Hello");
        Scanner in = new Scanner(System.in);
        int a = in.nextInt();
        int[] arr = new int[a];
        for(int i = 0;i<a;i++){
            arr[i]=in.nextInt();
        }
        System.out.println(GetMinArrSum2(arr));
    }
}

题目3 : Exam15_MaxHeap
时间限制:5000ms
单点时限:1000ms
内存限制:256MB

描述

给定一个数组,求最小的K个数。由于数组规模很大,请精心设计算法。
输入

第一行:N(1<N<=100000),代表数组的长度
第二行:K(<=1000,<N),代表求从小到大的K个数
第三行:N个整数,作为数组的元素,空格分开
输出

从小到大输出K个数组中最小的数,空格隔开
样例输入

10
3
1 3 4 2 6 7 8 10 11 12

样例输出

1 2 3

AC代码

#include<stdio.h>
//  k 个循环,求出最小的k个数即可结束
void px(int*a,int n,int k)
{
    int jj,j;
    for(jj=0;jj<k;jj++)
    {
        for(j=n-2;j>=jj;j--)
        {
            if(a[j]>a[j+1])
            {
                a[j]+=a[j+1];
                a[j+1]=a[j]-a[j+1];
                a[j]=a[j]-a[j+1];
            }
        }
        printf("%d ",a[jj]);
    }
        
}
main()
{
    int n,a[100000],i,s=0,k;
    scanf("%d",&n);
    scanf("%d",&k);
    for(i=0;i<n;i++)
        scanf("%d",&a[i]);
    px(a,n,k);
    return 0;
} 

题目4 : Exam16_CombineString
时间限制:5000ms
单点时限:1000ms
内存限制:256MB

描述

给定一个字符串类型的数组strs,请找到一种拼接顺序,使得将所有的字符串拼接起来组成的大字符串是所有可能性中字典顺序最大的,并输出这个大字符串。
输入

第一行:N(1<N<=100),代表数组的长度
第二行:N个字符串,作为数组的元素,空格分开,字符串长度<=10
输出

字典序最大的大字符串
样例输入

5
a ac ab def d

样例输出

defdacaba

AC代码

#include<stdio.h>
#include<string.h>
main()
{
    char str[101][11];
    char tp1[21],tp2[21],tmp[11];
    int n,i,f,j;
    scanf("%d",&n);
    for(i=0;i<n;i++)
        scanf("%s",&str[i]);
        
    for(j=n-1;j>0;j--)
    for(i=0;i<j;i++)
    {
        strcpy(tp1,str[i]);
        strcat(tp1,str[i+1]);   //  tp1= str[i]+str[i+1]
        strcpy(tp2,str[i+1]);
        strcat(tp2,str[i]);     //  tp2= str[i+1]+str[i]
        
        f=strcmp(tp1,tp2);  //  比较结果给f
        if(f<0)
        {   //  交换
            strcpy(tmp,str[i]);
            strcpy(str[i],str[i+1]);
            strcpy(str[i+1],tmp);
        }
    }
    
    for(i=0;i<n;i++)
        printf("%s",str[i]);
    return 0;
} 

题目5 : Exam17_NewOrder
时间限制:5000ms
单点时限:1000ms
内存限制:256MB

描述

一般我们在对字符串排序时,都会按照字典序排序。当字符串只包含小写字母时,相当于按字母表"abcdefghijklmnopqrstuvwxyz"的顺序排序。

现在我们打乱字母表的顺序,得到一个26个字母的新顺序:bdceafghijklmnopqrstuvwxyz,代表'b'排在'd'前,'d'在'c'前,'c'在'e'前……

给定N个字符串,请你按照新的字母顺序对它们排序。
输入

第一行包含一个整数N。(1 <= N <= 1000)

第二行包含26个字母,代表新的顺序。

以下N行每行一个字符串S。 (|S| <= 100)
输出

按新的顺序输出N个字符串,每个字符串一行。
样例输入

5
bdceafghijklmnopqrstuvwxyz
abcde
adc
cda
cad
ddc

样例输出

ddc
cda
cad
abcde
adc

半AC只跑了80分 还得改进。

#include<stdio.h>
#include<string.h> 

char qj[1001][101];///  将输入数组化为abc..并保存
int sum=0;

void change(char *aa,char *bb,int len,char *tp)// 对应abc。。保存
{ 
    int i,j,jj;
    for(j=0;j<len;j++)
    for(i=0;i<26;i++)
    {
        if(tp[j]==aa[i])
        {
            tp[j]=bb[i];
            break;
        }
    }
    strcpy(qj[sum++],tp);
}
main()
{
    
    char tp[101];
    char str[1001][101];    //  保存输入的数组
    char aa[26],bb[26];
    int n,i,len,f;
    
    scanf("%d",&n);
    
    scanf("%s",&aa);    //  a 新顺序
    
    for(i=0;i<n;i++)
        scanf("%s",&str[i]);    //  多行字符串 
        
    for(i=0;i<26;i++)
        bb[i]='a'+i;    //  b 原顺序 
        
    for(i=0;i<n;i++)
    {
        strcpy(tp,str[i]);
        change(aa,bb,strlen(str[i]),tp);
    }
    for(sum=n-1;sum>0;sum--)    
    for(i=0;i<sum;i++)
    {
        //  比较 排序 
        f=strcmp(qj[i],qj[i+1]);
        if(f>0)
        {
            strcpy(tp,qj[i]);
            strcpy(qj[i],qj[i+1]);
            strcpy(qj[i+1],tp);
            // 同时对str[]排序
            strcpy(tp,str[i]);
            strcpy(str[i],str[i+1]);
            strcpy(str[i+1],tp);
        }
    }
    for(i=0;i<n;i++)
        printf("%s\n",str[i]);  //  输出  
    return 0;
} 

相关文章

  • 算法很美--查找与排序

    题目1 : Exam13_Median时间限制:5000ms单点时限:1000ms内存限制:256MB 描述 给定...

  • 排序算法的基本操作:两两交换数组中元素

    查找 vs 排序 比较查找与排序算法 说起来查找算法和排序算法从功能到使用目的都大有不同,但其实我们将要学习的(比...

  • Chapter 2 Foundation of Algorith

    Chapter 2 插入排序 线性查找 选择算法 归并排序算法 二分查找算法 冒泡排序 插入排序 循环不...

  • 排序查找c++

    排序算法 选择排序 顺序查找 二分查找

  • 3.2 快速排序算法

    Chapter3: 更好的查找与排序算法 2. 快速排序算法 1. 什么是快速排序算法 分解数组 A[p..r] ...

  • 其难杂症

    排序 冒泡排序,快速排序 查找算法 二分查找算法 Array方法 push/unshift,pop/shift,m...

  • 数据结构+算法

    排序算法 基本排序:冒泡、选择、插入 高级排序希尔、归并、快速 检索算法 顺序查找、二分查找 高级算法 动态规划斐...

  • java排序和查找算法

    一、排序算法 二、查找算法

  • 基础算法(查找 , 排序)

    算法分析 渐进符号 - (O , Ω , θ) 查找算法 二分查找 - O(logn) 排序算法 直接插入排序 -...

  • 消息传递-缓存-转发流程

    消息传递 缓存查找 哈希查找 三种查找方式缓存 -> 哈希算法查找当前类 -> 已排序 二分查找算法 未排序 ...

网友评论

      本文标题:算法很美--查找与排序

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