Contains Duplicate II

Given an array of integers and an integer k, find out whether there there are two distinct indices i and j in the array such that nums[i] = nums[j] and the difference between i and j is at most k.

题目大意：

给定一个整数数组nums与一个整数k，当且仅当存在两个不同的下标i和j满足nums[i] = nums[j]并且| i - j | <= k时返回true，否则返回false。

Contains Duplicate

Total Accepted: 20833 Total Submissions: 57794

Given an array of integers, find if the array contains any duplicates.
Your function should return true if any value appears at least twice in the array, and it should return false if every element is distinct.

指针数组

1
2
3
4
5
6
7
8
9
10
11

main()

{

int a[5]={1,2,3,4,5};

int *ptr=(int*)(&a+1);

printf("%d,%d",*(a+1),*(ptr-1));

}

输出：2,5

归并排序

运行时间是O(NlogN),但是很难用于主存排序。主要是因为合并两个排序的表需要线性附加内存，在整个算法中还要花费将数据拷贝到临时数组再拷贝回来这样的附加的工作，其结果严重影响了排序的速度。
合并适合于外部排序

数学基础

T(N)= O( f(N) ) T(N)的增长率 <= f(N)的增长率
T(N)= Ω( f(N) ) T(N)的增长率 >= f(N)的增长率
T(N)= θ( f(N) ) T(N)的增长率 = f(N)的增长率
T(N)= o( f(N) ) T(N)的增长率 < f(N)的增长率

希尔排序

又称缩小增量排序，只要最后一个增量是1，任何的序列都是可行的。在使用增量H之后，对于每一个i,我们有A[i]<=A[i+H],及所有相隔H的元素都被排序

快速排序

快速排序（quicksort）是在实践中最快的已知排序算法，平均运行时间是O(NlogN),最坏的性能为：O(N^2).