WC142 排序

谁践踏了优雅 2022-09-16 00:15 118阅读 0赞

# 题目 #

给定一个长度为 n 的数组，请你编写一个函数，返回该数组排序后的结果。

数据范围： 0 ≤n≤1000000，数组中每个元素都满足 0 ≤val≤1000000000  
要求：空间复杂度 O(n)，时间复杂度 O(nlogn)

# 实例 #

> 输入：\[5,2,3,1,4\]  
> 输出：\[1,2,3,4,5\]

# 解题思路 #

> 为达复杂度要求，采用归并排序，归并排序空间复杂度 O(n)，时间复杂度 O(nlogn)

# 代码 #

import java.util.*;
    
    
    public class Solution { 
    
        /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * 将给定数组排序 * @param arr int整型一维数组 待排序的数组 * @return int整型一维数组 */
        public int[] MySort (int[] arr) { 
            // write code here
            int[] res = new int[arr.length];
            sort(arr,0,arr.length-1,res);
            return res;
        }
        
        public void sort(int[] arr,int l,int r,int[] data){ 
            if(l<r){ 
                int middle = (l+r)/2;
                sort(arr,l,middle,data);
                sort(arr,middle+1,r,data);
                merge(arr,l,middle,r,data);
            }
        }
        
        public void merge(int[] arr,int l,int m,int r,int[] data){ 
            int i = l;
            int j = m + 1;
            int t = 0;
            while(i<=m &&j<=r){ 
                if(arr[i]<=arr[j]){ 
                    data[t++] = arr[i];
                    i++;
                }else{ 
                    data[t++] = arr[j];
                    j++;
                }
            }
            while(i<=m){ 
                data[t++] = arr[i++];
            }
            while(j<=r){ 
                data[t++] = arr[j++];
            }
            t = 0;
            while(l<=r){ 
                arr[l++] = data[t++];
            }
        }
    }

2021年10月13日

发表评论取消回复

表情：

评论列表（有 0 条评论，118人围观）

还没有评论，来说两句吧...

相关阅读

相关 [WC2018]通道

[题目][Link 1] 三棵树真的能让人自闭第一棵树常规做法，直接边分治，处理出每个点到分治边的距离\\(dis\_i\\)，同时黑白染色第二棵树还是常规做法，直接

雨点打透心脏的1/2处/ 2023年10月11日 11:16/ 0 赞/ 32 阅读

相关 Flink版本WC

Flink版本WC wc是一个非常经典的大数据例子，下面我们运行一下wc flink run -m yarn-cluster -yn 4 -yjm 102

深藏阁楼爱情的钟/ 2022年12月27日 04:45/ 0 赞/ 131 阅读

相关 wc命令

linux中的wc命令(word count) 可以用来统计计数， eg1:统计文件的行数 wc -l filename eg2: 统计文件中某一个

Dear 丶/ 2022年10月22日 14:50/ 0 赞/ 179 阅读

相关 wc命令

Linux系统中的wc(Word Count)命令的功能为统计指定文件中的字节数、字数、行数，并将统计结果显示输出。 1．命令格式： wc \[选项\]文件... 2．命

朱雀/ 2022年09月17日 14:19/ 0 赞/ 166 阅读

相关 WC142 排序

题目给定一个长度为 n 的数组，请你编写一个函数，返回该数组排序后的结果。数据范围： 0 ≤n≤1000000，数组中每个元素都满足 0 ≤val≤10000000

谁践踏了优雅/ 2022年09月16日 00:15/ 0 赞/ 119 阅读

相关 linux命令 wc

Linux系统中的wc(Word Count)命令的功能为统计指定文件中的字节数、字数、行数，并将统计结果显示输出。 1．命令格式： wc \[选项\]文件... 2．命

落日映苍穹つ/ 2022年08月22日 00:10/ 0 赞/ 168 阅读

相关 linux wc命令

功能：统计文本信息数量参数如下： -c, --bytes 打印字节数 -m, --chars 打印字符数量 -l, --lines 打

Bertha 。/ 2022年05月30日 10:42/ 0 赞/ 163 阅读

相关 WC2019游记

day-4 WC居然还要把THUWC的被子搬到另一个寝室楼...早上就忙着跑来跑去，顺便去报了个到。话说WC居然也有签名板这种东西，犹豫了一下还是把我的名字签上了。为

淩亂°似流年/ 2022年01月05日 22:37/ 0 赞/ 199 阅读

相关 linux wc命令

转自：[https://www.cnblogs.com/peida/archive/2012/12/18/2822758.html][https_www.cnblogs.com

绝地灬酷狼/ 2021年09月27日 06:42/ 0 赞/ 254 阅读

相关 Linux wc命令

Linux wc命令用于计算字数。利用wc指令我们可以计算文件的Byte数、字数、或是列数，若不指定文件名称、或是所给予的文件名为"-"，则wc指令会从标准输入设备读取数据。

灰太狼/ 2020年05月26日 14:07/ 0 赞/ 628 阅读