s******t
发帖数: 150 | 1 ifstream input("story.txt");
vector words;
cout << words.size() << endl;
if(!input)
cerr << "Could not open story.txt!\n";
else
{
string line;
while(getline(input,line))
{
// get single word from each line
istringstream stream(line);
string word;
while(stream >> word)
words.push_back(word);
}
}
//close file
input.close();
cout << "Before sort(), ... 阅读全帖 |
|
m*******a
发帖数: 192 | 2 【 以下文字转载自 SanFrancisco 讨论区 】
发信人: maladonaa (hello), 信区: SanFrancisco
标 题: sorting问题求教。
发信站: BBS 未名空间站 (Thu Oct 14 20:27:51 2010, 美东)
If I have N numbers
and I want to find out the top X of them
and sort the top X from largest to smallest,
what kind of sorting algorithm would you recommend? thanks |
|
m*******a
发帖数: 192 | 3 【 以下文字转载自 SanFrancisco 讨论区 】
发信人: maladonaa (hello), 信区: SanFrancisco
标 题: sorting问题求教。
发信站: BBS 未名空间站 (Thu Oct 14 20:27:51 2010, 美东)
If I have N numbers
and I want to find out the top X of them
and sort the top X from largest to smallest,
what kind of sorting algorithm would you recommend? thanks |
|
h*******e
发帖数: 68 | 4 ☆─────────────────────────────────────☆
antonioxy (有绿卡不如学CS) 于 (Tue Jul 25 20:56:28 2006) 提到:
好歹都是很资深的程序员了，还犯这种错误，一段大程序改下来真是烦死，比如说这么个
东东：
data d1;
input a b c;
datalines;
1 2 3
1 5 6
1 2 3
2 4 6
;
proc sort data=d1 nodup; by a; run;
这个sort就错了，为什么，运行一下就知道，根本不能去掉第三行重复的数据，正确的应
该
是
proc sort data=d1 nodup; by _all_; run;
或
proc sql;
create table d1 as
select distinct * from d1 order by a;
quit;
sql更好一点因为可以规定排序的变量。
☆─────────────────────────────────────☆
papertigra (长工胖头猪) 于 (T |
|
h******t
发帖数: 872 | 5 Think of what The Times reported last February: At little Grinnell College
in rural Iowa, with 1,600 students, “nearly one of every 10 applicants
being considered for the class of 2015 is from China.” The article noted
that dozens of other American colleges and universities are seeing a similar
surge as well. And the article added this fact: Half the “applicants from
China this year have perfect scores of 800 on the math portion of the SAT.”
...........
A Theory of Everything (Sort Of)
By THOMAS... 阅读全帖 |
|
|
s*********o
发帖数: 409 | 7 他那个是sort整数，我需要sort的是0.几的小数，是不是改成float就可以了？
20- |
|
M*****n
发帖数: 16729 | 8 请有经验的faculty 给点意见。
因为写grant proposal 有关，时间比较紧。
多谢。
【 以下文字转载自 Biology 讨论区 】
发信人: Morphin (莫非-白衣“追鱼”郎), 信区: Biology
标 题: 问个FACS cell sorting的问题
发信站: BBS 未名空间站 (Sat Apr 16 13:26:14 2011, 美东)
FACS能不能sort aggregates of cells?
不是single cell, FACS 机器能行吗？
请各位有经验的指教。谢谢。 |
|
k*k
发帖数: 49 | 9 yes... but with additional space for min-heap
considering the complexity of constructing such a table in addition to the n
^2 log n sorting complexity...
young's table is really not a good way to tackle sorting problem.... |
|
l***i
发帖数: 1309 | 10 For your second problem, why not dump the smallest numbers to A and the rest
to B(swap max in A with min in B), then sort A, B separately to get O(nlogn
). Heap sort can do this since you do not have O(n) extra storage. |
|
x***y
发帖数: 633 | 11 A[n/2]=6, B[n/2]=33, C[n/2]=100, So A':6 10 18 C': 7 9
To find the median M' of A' C', O(log(max(|A'|, |C'|)))=O(logn).
if M' < B[n/2], B is left with B[22 28 33], and find data in A'less than M'
, find data in C' less than M', O(logn), and eleminate them.....
All problems of this kind is essentially 2 array problem, and the time
efficiency is O(logn) * time for finding the median and delete operation in each array. For sorted array, 2nd term is O(1), but for an partially sorted array A'+C',th |
|
k**********i
发帖数: 177 | 12 我觉得是吧。。merge sort。。。分成 buck。。。sort， 然后再merge？ |
|
K******g
发帖数: 1870 | 13 那些quick, merge,heap sort, 都是基于数组的，如果给个list，怎么sort呢？请问谁
能提示一下，多谢了。 |
|
f*********5
发帖数: 576 | 14 这样可以不？
void sort(stack &st)
{
if (st.IsEmpty())return;
int temp=st.top();
st.pop();
sort(st);
Insert(st,temp); //insert temp to the right position in st
//here we can use a list to temporarily store
//the nodes whose value less than temp
} |
|
I**********s
发帖数: 441 | 15 The key is:
If the first element is less than the midpoint, the first half of the array
is correctly sorted. If the midpoint is less than the last element, the
second half of the array is correctly sorted. |
|
s*******t
发帖数: 248 | 16 问merge sort 和 quick sort 分别在什么情况下用？
如果n = 10000, 用哪个？
如果n 超大，用那个？
为什么？谢谢！ |
|
p**********s
发帖数: 115 | 17 n大的话用merge sort，几台机器分别sort，然后再merge |
|
|
s*******e
发帖数: 93 | 19 OK. So how about:
for (int i=0; i
for (int i=nl; i
left[nl] = right[nr-1] + 1;
right[nr] = left[nl-1] + 1;
Since left is sorted, right is sorted,
and you just want to make sure that the sentinel of left is larger than
everything in right
and the sentinel of right is larger than everything in left |
|
h***n
发帖数: 276 | 20 1) imagine virtual K arrays store in one array, i-th element in A belong to
array A_{i%K}
2) to sort the array A, do K-way merge
A[0] .... A[n]
kind of "sort" it so that
A[i] < A[j] where j> i+K, and i in [0, n-K]
I remember working it out before, but forgot |
|
n**z
发帖数: 155 | 21 Java? Arrays only have a sort function |
|
s******d
发帖数: 61 | 22 You have 100 files, each containing 10G sorted integers. How to merge all
integers into one sorted file?
这题以前见过,现在又没思路了...求解 |
|
i**********e
发帖数: 1145 | 23 singly linked list 就可以做到 n log n 了。
用merge sort，in-place merge。
linked list 没有像数组那样可以 random access in O(1)，quick sort 不适用。 |
|
F*****e
发帖数: 331 | 24 list str= new List();
str.Add("Milk");
str.Add("Steak");
str.Add("Fish");
str.Sort();
系统自己排序结果是：Fish Milk Steak（升序）
str.Sort(SortDESC); <-----这种写法是什么意思啊？
int SortDESC(string x, string y)
{
return String.Compare(x, y) * -1;
}
结果是：Steak Milk Fish(降序) |
|
j********r
发帖数: 453 | 25 two unordered array, one long,n , one short, m, sort them into a large array
. Someone say that we can sort the short array, it's mlogm, and binary
search and insert the long, the total is nlogm. but i am not clear about the
insert part, how it can be nlogm.
If there is a better algorithm, please share.
Thank for helps. |
|
g****v
发帖数: 971 | 26 问题是在第5步，比如， 1G data, 100M memory,
1: divide into 10 parts.
2: sort 10 parts each in memory then write back to hard drive.
3: read 10M from each part (100M)
4: merge sort the 10 10M and write back the first 10M.
5: get 10M from one of the 100M parts in hard drive
问题是现在有10个100M被排序好了保存在硬盘上，然后每个100M取出10M在内存里面排序，然后把第1
个10M存在硬盘上，然后需要从那些100M里面取10M，问题是取10M的时候从哪个100M里面取？
谢谢 |
|
w****o
发帖数: 2260 | 27 heap sort是吗？
quick sort肯定不是了。
谢谢！ |
|
f*******n
发帖数: 12623 | 28 merge sort
timsort
binary tree sort |
|
c****g
发帖数: 85 | 29 Question: Find the k-th Smallest Element in the Union of Two Sorted Arrays
Given two sorted arrays A, B of size m and n respectively. Find the k-th
smallest element in the union of A and B. You can assume that there are no
duplicate elements.
http://www.leetcode.com/2011/01/find-k-th-smallest-element-in-u
如果A组划k/2，B组划k/2来比较。为方便解释，这里先假设k为偶数,并且m,n>k/2.
如果不满足这些条件，在计算index的时候，会考虑这些情况。
if A[k/2 - 1] == B[k/2 -1] done.
if A[k/2 - 1] > B[k/2 -1]
那么在A[k/2 + 1 - k] 和 B[0 k/2 - 1] 里取k/2 smallest number。
... 阅读全帖 |
|
w****x
发帖数: 2483 | 30 对阿， median of 2 sorted array 就是kth element of two sorted array的变体，
后者简洁多了， 但是收敛速度不一样啊 |
|
w****x
发帖数: 2483 | 31 对阿， median of 2 sorted array 就是kth element of two sorted array的变体，
后者简洁多了， 但是收敛速度不一样啊 |
|
f*******w
发帖数: 1243 | 32 已知7个数，关系如下
x1 > x2 > x4
x2 > x5
x1 > x3 > x6
x3 > x7
问怎么排序是最优的，最优的方法worst case需要多少次比较
我是用merge sort的想法，先merge
x2, x4 和 x2, x5
需要1次比较 (x4 和 x5)
然后merge
x3, x6 和 x3, x7
需要1次比较 (x6 和 x7)
然后merge
x2, x4, x5 和 x3, x6, x7
需要5次比较（merge sort：3+3-1次比较）
所以总共是7次比较
但是不知道怎么证明是最优的？或者这样不是最优的？ |
|
f*******4
发帖数: 64 | 33 Given two sorted integer arrays A and B, merge B into A as one sorted array.
Note:
You may assume that A has enough space to hold additional elements from B.
The number of elements initialized in A and B are m and n respectively.
Note里说，A有额外空间,用来合并。
但我觉得必须额外开一个m的空间，除了A[m+n]外，放一些需要swap的变量。
这题最小的空间复杂度能到多少？ |
|
c*****a
发帖数: 808 | 34 我写了个类似counting sort的
public static int[] sort(int ar[], int n){
int[] buff = new int[n];
for(int i =0; i
buff[ar[i]]++;
int i=0,j=0;
int[]res = new int[ar.length];
while(j
if(buff[j]>0){
res[i++] = j;
buff[j]--;
}
else j++;
}
return res;
}
感觉worst case,所以的elements都在同一个index,while loop走2n次...
这个是不是linear time O(n) |
|
e******i
发帖数: 106 | 35 这是我写的insert intervals的code.
想问下，这里面sort的O(n)是多少？
/**
* Definition for an interval.
* public class Interval {
* int start;
* int end;
* Interval() { start = 0; end = 0; }
* Interval(int s, int e) { start = s; end = e; }
* }
*/
public class Solution {
public ArrayList insert(ArrayList intervals,
Interval newInterval) {
// Start typing your Java solution below
// DO NOT write main() function
if (newInterval == null) {
retur... 阅读全帖 |
|
s****A
发帖数: 80 | 36 是不是merge sort比较好写而insertion sort比较难写？ |
|
s****A
发帖数: 80 | 37 不知道啊
万一有个情况是一堆不太长的链表
考官又说quick sort带来的提速没多少
不如换个比较不容易写错的sort
有可能吗？ |
|
o****o
发帖数: 23 | 38 既然是sorted（假设是从大到小），就用一个size n的最大堆，每次取出最大的，然后
加入该元素所在数组的后续元素，heapify之后再取，直到取到top K停止。
如果不是sorted，那就得用size k的最小堆，遍历所有array的剩余元素，分别与最小
堆的root比较，大于root就替换root，heapify一下，小于等于就跳过。 |
|
s********x
发帖数: 914 | 39 比如quick sort吧。
如果用Parallel threads把array分成几个section来sort，应该比nlog(n)更快吧。这
样不是很多interview问题就不是最优解了吗？ |
|
x*****0
发帖数: 452 | 40 bool myComparision1(vector x, vector y);
vector > result;
sort(result.begin(), result.end(), myComparision1);
用GCC4.6.1编译，在自己的电脑上没有问题。
leetocde 一直给出如下错误：
Line 77: no matching function for call to 'sort(std::vector
>::iterator, std::vector >::iterator,
overloaded function type>)' |
|
g********E
发帖数: 178 | 41 quick sort还是merge sort?
二分法每次少一半，三分法每次只少了1/3 |
|
i******t
发帖数: 22541 | 42 好象是 kth of two sorted arrays
容易些
median of two sorted arrays 剧难 具难。。。。。。。。 |
|
|
f****p
发帖数: 18483 | 44 笨死！在那些O(nlogn)的算法中，有两个常数就是说cost = A*(nlogn) + B。
on average，quick sort的这两个常数都是最小的。 |
|
|
p*****2
发帖数: 21240 | 46 quick sort O(1) memory吧？ |
|
D****6
发帖数: 278 | 47 首先每个array都是sorted是吧，arr1和2merge完之前没其他arr的事啊，完后生成新的
sorted arr在和3 merge. 还有为什么“ array 1里放的都是比array2小的”？你来个
简单的实际的例子。 |
|
p*****e
发帖数: 537 | 48 bubble sort应该是可以的，merge sort也是可行的只是比较麻烦。还有别的更好的方
法吗？ |
|
u*****o
发帖数: 1224 | 49 只知道bubble sort怎么做，请问愿意分享merge sort怎么写吗？ |
|
|
