您的位置:js12345金沙官网登入 > 网络编程 > 【金沙澳门娱乐网址】Leetcode - Read N Characters Gi

【金沙澳门娱乐网址】Leetcode - Read N Characters Gi

2019-10-08 04:59

My code:

计数排序是一种非比较的排序,这种方法思路大概是先算出待排序数据里面的数字分别出现多少次,然后再依据这个存放进新的数组里面,输出这个数组,排序也就完成了。时间复杂度为o(n+k),很多人说是o(n),但其实只是接近而已。其中里面的n是排序的数据个数,而k是排序中最大的值,可想而知,在n确定的情况下,k的值越小,时间复杂度越低,例如就算n很小,但排序数是{2,5,3,10000}的话,那也需要很多时间,此排序方法就不怎么适用了。
程序例子:(主要参考排序核心方法,其他的写得不够好)
<pre><code>

/* The read4 API is defined in the parent class Reader4. int read4(char[] buf); */public class Solution extends Reader4 { /** * @param buf Destination buffer * @param n Maximum number of characters to read * @return The number of characters read */ public int read(char[] buf, int n) { char[] arr = new char[4]; int counter = 0; int num = 4; while (num == 4 && counter < n) { num = read4; for (int i = counter; i < n && i < counter + num; i++) { buf[i] = arr[i - counter]; } counter = Math.min(n, counter + num); } return counter; }}

include <iostream>

using namespace std;
//-------------------------
int data[100];//全局变量,用来存放待排序数据
int array_length;//数组的长度
int array_max;//数组中最大的值,也就是k
//---------------------------------
//初始化数组
void Init_array()
{
cout<<"Input:(End with 1000)";
for(int i=0;; i++)
{
cin>>data[i];
if(data[i]==1000)
{
array_length = i;//由此获得数组长度
break;
}
}
}
//-----------------------------------
//求数组中最大的数
void max_array()
{
int t;
array_max = data[0];
for(int i=0; i<array_length-1; ++i)
{
if(data[i]<data[i+1])
{
array_max = data[i+1];
}
else
{
t = data[i];
data[i] = data[i+1];
data[i+1] = t;
}
}
}
//----------------------------------
//计数排序
//参数分别是1.待排序数组,2.数组长度,3.待排序数组中最大的值,也就是k
void sort_counter(int d[], int n, int k)
{
int i, j = 0,p = 0;
// 实际需要的空间比K大1
k++;
//辅助数组,当然也可以用其他编程技术来代替
int counter[100] = {0};
// 计数
for(i=0; i<n; ++i)
{
p = d[i];
counter[d[i]]++; //counter数组下标为排序的数,下标对应的数组值为这个数出现的次数
}
//将计数结果保存到待排数据数组
for(i=0; i<k; ++i)
{
while(counter[i]-- > 0) //将出现的数字以及次数,依次放到数组中
{
d[j++] = i;
}
}
}
//主函数
int main(void)
{
Init_array();
max_array();
sort_counter(data, array_length-1, array_max);
int i;
for(i=0; i<array_length; ++i)
{
cout<<data[i]<<" ";
}
cout<<endl;
return 0;
}
</code></pre>

reference:https://discuss.leetcode.com/topic/52449/java-solution-easy-to-understand

没能自己做出来。没理解题目的意思。后来才知道什么意思。其实就是每次读4个,读出 n 个 拷贝到 char[] 里面去。

本文由js12345金沙官网登入发布于网络编程,转载请注明出处:【金沙澳门娱乐网址】Leetcode - Read N Characters Gi

关键词: