D*******a
发帖数: 3688 | 1 radix sort号称是O(N)的排序，小弟有点不明白
假如排1~9999，那么需要排4遍，每遍是N次运算
排1～99999，那么需要5遍
如果排1～N，那么应该是需要Nlog10(N)遍才对啊
为什么得出O(N)的结论？ |
|
y***u
发帖数: 101 | 2 radix sort 在ram model下还是O(n log n)啊，只不过一般人说机器
的word size是fixed，所以O(n)，其实不严格。RAM model下认为一个
word有O(log n)个bit。
不过在RAM model下的确是可以在小于O(n log n)时间内完成排序的。 |
|
w**z
发帖数: 8232 | 3 我再贴一下Java的sourcecode。不懂为什么要把正数转成负数再查溢出呢？有什么好处？
code里有Author的comments
// Accumulating negatively avoids surprises near MAX_VALUE
/**
* Parses the string argument as a signed integer in the radix
* specified by the second argument. The characters in the string
* must all be digits of the specified radix (as determined by
* whether {@link java.lang.Character#digit(char, int)} returns a
* nonnegative value), except that the first character may be an
* ASCII minus sig... 阅读全帖 |
|
w**z
发帖数: 8232 | 4 Source Code from Java
/*
* @author Lee Boynton
* @author Arthur van Hoff
* @author Josh Bloch
* @version 1.92, 04/07/06
* @since JDK1.0
*/
/**
* Parses the string argument as a signed integer in the radix
* specified by the second argument. The characters in the string
* must all be digits of the specified radix (as determined by
* whether {@link java.lang.Character#digit(char, int)} returns a
* nonnegative value), except that the first character may be an
* A... 阅读全帖 |
|
g*****g
发帖数: 34805 | 5 我来贴标准答案了。把radix hardcode成10就行。
public static int More ...parseInt(String s, int radix)
440 throws NumberFormatException
441 {
442 if (s == null) {
443 throw new NumberFormatException("null");
444 }
445
446 if (radix < Character.MIN_RADIX) {
447 throw new NumberFormatException("radix " + radix +
448 " less than Character.MIN_
RADIX");
449 }
450
451 if (radix > Character.... 阅读全帖 |
|
y*****z
发帖数: 9 | 6 我用了 基序排序， 这样能达到线性时间。
复杂度是 max(O(M)，O(N))
M是date的最大的数
N是数组的长度
code wins arguments.
欢迎拍砖
#define GREEDY_EVENT
#ifdef GREEDY_EVENT
#include
#include
#include
using namespace std;
int main(){
const int n = 5;
int sstart[n] = {1,8,2,11,15};
int eend[n] = {4,9,6,14,18};
for(int i=0;i
cout<<"("<
}
cout<
const int MAXDATE = 100;
int radix[MAXDATE]={0};
int final[n];
for(int ... 阅读全帖 |
|
y*****z
发帖数: 9 | 7 我用了 基序排序， 这样能达到线性时间。
复杂度是 max(O(M)，O(N))
M是date的最大的数
N是数组的长度
code wins arguments.
欢迎拍砖
#define GREEDY_EVENT
#ifdef GREEDY_EVENT
#include
#include
#include
#include
using namespace std;
int main(){
srand(size_t(time(0)));
const int n = 5;
int sstart[n] = {1,8,2,11,15};
int eend[n] = {4,9,6,14,18};
for(int i=0;i
for(int i=0;i
for(int i=0;i
cout<<"("<阅读全帖 |
|
f**d
发帖数: 768 | 8 这是一本计算神经科学的优秀著作，全文拷贝这里（图和公式缺），有兴趣的同学可以
阅读
如需要，我可以分享PDF文件（－－仅供个人学习，无商业用途）
From Computer to Brain
William W. Lytton
From Computer to Brain
Foundations of Computational Neuroscience
Springer
William W. Lytton, M.D.
Associate Professor, State University of New York, Downstato, Brooklyn, NY
Visiting Associate Professor, University of Wisconsin, Madison
Visiting Associate Professor, Polytechnic University, Brooklyn, NY
Staff Neurologist., Kings County Hospital, Brooklyn, NY
In From Computer to Brain: ... 阅读全帖 |
|
|
t*******r
发帖数: 22634 | 9 proof：“in radix 8 place value, 77*100 = 7700”
proof by expand place-value to algebraic expression,
then convert back to place-value:
(The following proof use radix-8 algebraic expression)
77 * 100
= ( 7*((10)^1) + 7*((10)^0) ) * ((10)^2)
= 7*((10)^1)*((10)*2) + 7*((10)^0)*((10)^2)
= 7*((10)^3) + 7*((10)^2)
= 7700
(Note there exist a radix-10 algebraic expression
proof, (not presented here), usually for lower-grader
kids that unable to operate in "radix-neutral" mode
while comprehend/perform alge... 阅读全帖 |
|
c**i
发帖数: 6973 | 10 Edward Rothstein, Masters of Math, From Old Babylon; A precursor to the
theoretical flowering of Greek math. New York Times, Nov. 27, 2010.
http://www.nytimes.com/2010/11/27/arts/design/27tablets.html?_r=1&scp=3&sq=cuneiform&st=cse
Note:
(a) Pythagoras (c. 570- c. 495 BC)
Wikipedia
(b) The report states, "But Neugebauer, and then his many students and
rivals, also showed how sophisticated Babylonian mathematics was and how
many similarities existed to later Western systems ?if, that is, you coun... 阅读全帖 |
|
i**a
发帖数: 98 | 11 From Wikipedia
The itoa (integer to ASCII) function is a widespread[citation needed] non-
standard extension to the standard C programming language. It cannot be
portably used, as it is not defined in any of the C language standards;
however, compilers often provide it through the header while in
non-conforming mode, because it is a logical counterpart to the standard
library function atoi.
void itoa(int input, char *buffer, int radix)
itoa takes the integer input value input and conv... 阅读全帖 |
|
c**i
发帖数: 6973 | 12 Edward Rothstein, Masters of Math, From Old Babylon; A precursor to the
theoretical flowering of Greek math. New York Times, Nov. 27, 2010.
http://www.nytimes.com/2010/11/27/arts/design/27tablets.html?_r=1&scp=3&sq=cuneiform&st=cse
Note:
(a) Pythagoras (c. 570- c. 495 BC)
Wikipedia
(b) The report states, "But Neugebauer, and then his many students and rivals, also showed how sophisticated Babylonian mathematics was and how many similarities existed to later Western systems if, that is, you count... 阅读全帖 |
|
c****p
发帖数: 6474 | 13 第二题做个类似于accumulative sum的数组就可以了吧。。
S[n] = x0 + x1 + ... + xn
建S[n]是O(n)，而且是一遍lookup。
Cb(t) = S[t] - S[t-2];
Ca(t)应该类似。
for
and then the least significant digits. For example, {254, 257, 322} →{322,
254, 257}→{322, 257, 254}. What is the complexity of radix sort? In what
settings would radix sort be |
|
g**e
发帖数: 6127 | 14 你把作业题拿上来问，合适吗？
for
and then the least significant digits. For example, {254, 257, 322} →{322,
254, 257}→{322, 257, 254}. What is the complexity of radix sort? In what
settings would radix sort be |
|
q****x
发帖数: 7404 | 15 anyone know the answer of the following?
CLRS v3:
As Exercise 11.3-3 asks you to show, choosing m = 2^p - 1 when k is a
character string interpreted in radix 2p may be a poor choice, because
permuting the characters of k does not change its hash value.
11.3-3
Consider a version of the division method in which h(k) = k mod m, where
m = 2^p - 1 and k is a character string interpreted in radix 2^p. Show
that if we can derive string x from string y by permuting its characters,
then x and y hash to... 阅读全帖 |
|
k***t
发帖数: 276 | 16 看了一下，可能是这样。
Radix Sort：O(NumOfPassess*N)
Binary Radix Sort:NumOfPasses=LogN，当待排元素集接近所有穷尽时。 |
|
f*****e
发帖数: 2992 | 17 来自主题: JobHunting版 - A家面试题 先用中位数和四分数（三个数过两遍就可以找出来）或者干脆是随机选的elements，
inplace把数组平分成4个子数组，每个子数组有2^20/2^2=2^18个数,然后对每个子数
组做radix sort。radix sort需要与原数组相同大小的额外空间，还需要buckets用来
记录落入bucket里的数的数目。如果用16位counting，要记录2^16个buckets，每个
bucket 4个字节用来记录落在这个bucket的数的数目。算一算正好够了，因为2MB内存
可以存放
buckets 2^16 x 4 =256KB，加额外空间 2^18 x 4 = 2^20 = 1MB。 |
|
s****A
发帖数: 80 | 18 如果只找一般的SDE工作
是不是只需要看bubble sort, insertion sort, selection sort, merge sort，quick
sort, radix sort, heap sort，BST, Balanced tree, hashing 就够了？
我看的书还有如下章节:
shell sort
special-purpose sorts(Batcher's odd-even merge sort, sorting networks,
external sorting, parallel sort/merge)
radix search
external searching
这些还需要看吗？
谢谢！ |
|
b******g
发帖数: 77 | 19 字符串不用hash
Step1:
radix sort, don't need to divide into small files. radix sort knows
where to write in a file.
Step2:
min priority queue store the 100 highest frequency word.
hash_ |
|
s******y
发帖数: 936 | 20 今天上班到下午3点，实在是不想工作了，建了一个新的service，config了auto
deployment，不过说来Amazon 内部用的tool 应该是业界很高级的了吧，至少我知道比
微软的先进10 年。全自动，速度特别快， 这也是为什么把A定为现在的dream。 其实
前五年的工作我觉得，主要是学习，去一个能学习的地方，找到自己的方向，工资差不
多就够了，做sde 也发不了财（大牛除外）。
昨天发了小结1， 收到很多站内信，还有很多不认识的朋友猜到我是谁，谢谢你们保护
我的隐私。
然后打个广告，正在做startup， 需要angularjs， nodejs 的前台dev， 还需要一个
java 的后台dev。有兴趣可以站内，如果不是西雅图的人，可能要求会更高一点，西雅
图的非常欢迎，要求能吃苦，有毅力，技术怎么样还好，肯学，framework 和技术都搭
好了，现在差implementation。
好了说正事吧：
换工作历程：
这个工作是个小公司，工资不高，不能满足屌丝我的需求，所以开始了骑驴找马。
Amazon： 几个月之后Amazon直接来了一个邮件，说在网上看到我的简历，... 阅读全帖 |
|
m*****n
发帖数: 7450 | 21 yeah, but that's going in a loop
from wiki:
The number twelve, a highly composite number, is the smallest number with
four non-trivial factors (2, 3, 4, 6), and the smallest to include as
factors all four numbers (1 to 4) within the subitizing range. As a result
of this increased factorability of the radix and its divisibility by a wide
range of the most elemental numbers (whereas ten has only two non-trivial
factors: 2 and 5, with neither 3 nor 4), duodecimal representations fit more
easily tha... 阅读全帖 |
|
|
d*******g
发帖数: 36 | 23
Congratulations for so many high quality papers.
I know you are referring radix sorting.
But radix sorting cannot be used anywhere.
你怎么找到‘第m大的’if there are real numbers, even for integers? |
|
U*****e
发帖数: 505 | 24 Integer.parseInt(string, radix)
or
Long.parseLong(string, radix) |
|
c*****t
发帖数: 1879 | 25 Go read radix sort on wikipedia. O(nlogn) is the theoretical minimum
when only considering comparison operators. Radix sort works on integers
because of use of additional properties of integers.
so
sorting
() |
|
t****t
发帖数: 6806 | 26 你这就接近于胡搅蛮缠了
通常的说法, quicksort 平均O(nlogn),最差O(n^2), radix是O(n), hash也是O(n)
如果要谈细节,都可以找出毛病来
quicksort worse case O(nlogn)?可以啊,加一个大常数你干不干
radix, 样本空间很大怎么办
hash, 找不到好的函数怎么办 |
|
l*******r
发帖数: 1 | 27 下面的modString() 函数是干什么的？
有什么问题?
如何改正？
#include
#include
#include
#include
#include
typedef int int32;
typedef char int8;
void xorStringRounds(int8 *output, int8 *pbDataOne, const int8 *pbDataTwo
, int32 length)
{
int32 i = 0;
for(i=0; i
{
output[i] = (int8)(pbDataOne[i] ^ pbDataTwo[i]);
}
return;
}
void itoa( int32 num, int8 *alpha, int32 radix )
{
if( radix == 10 )
{
sprintf(alpha, |
|
b***e
发帖数: 1419 | 28 The trick for this question is use a variable-based radix sort.
In normal radix sort, the bases are fixed. This time use the
variable "n" as the sorting base. Concete soluction is as follows:
Rewrite each number in the representation of (x / n, x % n), where
the "/" represents integeral division, and "%" represents integeral
modulo, as in C. You can first use counting sort to sort the second
elements of all the pairs , and then sort the first element. This
takes O(n) time. |
|
m*******r
发帖数: 1701 | 29 附件B：被加利福尼亚卫生局鉴定的产品
1992年2月21日修订
一、含有有毒成分的药物
1.产品名称：保泰松
厂商： 泰国曼谷纽约化学药品公司
有毒成分：I，2-联苯1-3，5-dioxo-4-n-butylpyrazolidine；苯甲二氮
不良反应：死亡，粒细胞缺乏，抽搐，癫痫发作，精神错乱。
2.产品名称：追风透骨丸
厂商： 香港南宁制药有限公司
台湾(或其它地方的)寿星制药有限公司
有毒成分：保泰松、氨基比林、消炎痛、二氢氯噻、利眠宁、甲基睾丸酮、强的松、
苯甲二氮、chloro—zoxozone、醋氨酚、铅、镉。
不良反应：死亡，粒细胞缺乏，昏迷，镇静，男性征增强。
3.产品名称：朱砂安神丸
厂商： 中国兰州中药厂
有毒成分：汞
不良反应：死亡，肾病，肝病，腹泻。
4.产品名称：小儿止咳糖浆
厂商：Thai Charoen Bhaeaaj，泰国
有毒成分：氯霉素(氨胺苯醇)
不良反庆：粒细胞缺乏，贫血，虚脱，肝炎、呕吐，腹泻。
5.产品名称：红花油
厂商： Koong Yiek... 阅读全帖 |
|
G***i
发帖数: 150 | 30 知道numerical 范围的话 如果不是很多 可以用 bucket 或者 radix sort O(n)
complexity
一般的话 comparison sort 直接上quick sort好了 average O(nlogn) |
|
发帖数: 1 | 31 【川普当选】重塑白人至上主义「另类右翼运动」成美国大患
2016-11-16 陈冠东 美国华人
点击标题下「美国华人」加关注
【川普当选】重塑白人至上主义「另类右翼运动」成美国大患
编者按
川普在他当选后的第五天任命了他作为总统的左膀右臂：Reince Priebus为白宫幕僚长
，Steve Bannon为他的首席策略顾问。Bannon是美国所谓的「另类右翼」的白人至上主
义势力的领袖。到底何为「另类右翼」？Bannon成为川普的首席军师到底意味着什么？
我们转载香港01陈冠东先生的文章，做一个深度解读。
作者：陈冠东
刚当选美国总统的特朗普，自初选以来一直相当惹火，更被视为将美国白人丑陋一面全
都暴露出来的人物。虽然将特朗普的支持者，全都标签为「疯狂」、「种族主义」及「
排外」等，确实并不公允，但在特朗普的支持者中，确实存在着一股自称为「另类右翼
」（Alternative Right）的白人至上主义势力。今次大选，正正见证了这股力量在美
国社会的抬头，其所带来的政治和社会生态冲击，绝对不容忽视。
或许特朗普本人未必十分清楚「另类右翼运动」如何在美国社会崛起，但客观事实就是
特朗普... 阅读全帖 |
|
发帖数: 1 | 32 【 以下文字转载自 Military 讨论区 】
发信人: Lobsterparty (龙虾党), 信区: Military
标 题: 川普当选,重塑白人至上主义「另类右翼运动」成美国大患（转）
发信站: BBS 未名空间站 (Sat Nov 19 00:16:12 2016, 美东)
【川普当选】重塑白人至上主义「另类右翼运动」成美国大患
2016-11-16 陈冠东 美国华人
点击标题下「美国华人」加关注
【川普当选】重塑白人至上主义「另类右翼运动」成美国大患
编者按
川普在他当选后的第五天任命了他作为总统的左膀右臂：Reince Priebus为白宫幕僚长
，Steve Bannon为他的首席策略顾问。Bannon是美国所谓的「另类右翼」的白人至上主
义势力的领袖。到底何为「另类右翼」？Bannon成为川普的首席军师到底意味着什么？
我们转载香港01陈冠东先生的文章，做一个深度解读。
作者：陈冠东
刚当选美国总统的特朗普，自初选以来一直相当惹火，更被视为将美国白人丑陋一面全
都暴露出来的人物。虽然将特朗普的支持者，全都标签为「疯狂」、「种族主义」及「
排外」等，确实并不公允，但... 阅读全帖 |
|
H*M
发帖数: 1268 | 33 对,就是先sort一次,后面就好弄了
但是后面的一些coding循环处理细节花了时间
假如radix sort算O(n)的话,就是O(n), lol |
|
w********p
发帖数: 948 | 34 额觉着类似greedy algorithm里schedule的题
先按第一个值排序（O(n) or O(nlgn))， 然后比较二个值得value ( O(n) )
不过一个小时写radix我觉得很牛乐。 |
|
w********p
发帖数: 948 | 35 所以要O(n)的话，只能用radix的variation. 额是没法1hr高定 |
|
k***e
发帖数: 556 | 36 最简单的n^2，用类似radix tree？
即使nlogn好像也要借助suffix array，也不trivial
靠 谁考这个我当场和他拼了
血溅五步 哈哈
out |
|
k***e
发帖数: 556 | 37 汗啊 geniusxsy成了终极索引
恩 我猜是trie而不是bst 更准确的说 是用 radix tree
用时仅 n * avglenth
it is better than my method. |
|
m*****f
发帖数: 1243 | 38 内存O（N)???
Do you mean O(1)?
If has O(n) memory, count sort, bucket sort, radix sort all can do it ba. |
|
r**u
发帖数: 1567 | 39 O(N)。你这个不对吧，count sort要知道range，这个range可以是0-2^31-1。不是O(N)。bucket也不对吧。
radix我明白了，对的。 |
|
r**u
发帖数: 1567 | 40 That is a different question!
mudhoof说的radix sort solution是对的吧？did I miss something? 不过我觉得count/bucket sort不对。
t |
|
g*******y
发帖数: 1930 | 41 radix sort
每个数x可以表示为 {i,j,k} x=i*n^2 + j*n + k; |
|
d****i
发帖数: 4354 | 42 把数分解成i*n^2 + j*n + k要花不少时间吧？不如n^3有多少位就用多少位的radix呢？ |
|
h*********e
发帖数: 56 | 43 In that way, the number of digits will be O(lgN), instead of a constant 3;
and the time complexity of the radix sort depends on that.
呢？ |
|
B*****t
发帖数: 335 | 44 1. O(nlgn) can be achieved by using FFT under some conditions. But generally
the best algorithm to find a subset of 3 elements sum up
to a given value T is O(n^2). The relationship is like radix sort vs quick
sort. But I doubt the interviewers from MS would ask such kind of questions.
2. I don't think there is such kind of algorithms with O(m+n) complexity. |
|
l*f
发帖数: 218 | 45 radix sort,O(n*k)
你用hash map,当map增大时insert key的时间不是常数 |
|
v****s
发帖数: 1112 | 46 恩，那天我们组的老美也说了radix sort, o(nk). 但是我觉得我说的bitmap也是o(n),
interview也太tough了吧。。。 |
|
m******9
发帖数: 968 | 47 hash function通常有:
modulo
folding
mid-square function
extraction
radix transformation
collision的解决办法:
line probing
quadratic search
double hashing
chaining
bucket addressing |
|
B*******g
发帖数: 1593 | 48 老方法是一低一高两个指针往中间移
counting sort radix sort对正整数可以O(n) |
|
y*c
发帖数: 904 | 49 binary search的话，你要知道这些数的range吧, 然后用radix sort的方法扔掉一般少
的。否则的话，我觉得需要linear time. |
|
y*********e
发帖数: 518 | 50 来自主题: JobHunting版 - 一道面试题 不用额外空间，数组的每一个值又是在[0,100]区间的，用radix sort就可以了，
用O(n)的时间。sort好了之后再遍历一遍，就可以找到duplicate咯。 |
|
