剑指offer(1):数组
1 写作计划
最近在看《剑指offer》,发现自己有很多的数据结构与算法的基础知识要复习,《好书一起读(131):让写作更好》中提到用写作倒逼阅读,我很是赞同。所以,计划以《剑指offer》为中心,以记录复习心得目的,写一系列数据结构与算法的文章。
- 文章结构
文章从概念介绍切入,接着介绍相关的语言细节(以C语言和Python为主),最后以《剑指offer》中的编程题做结。
2 什么是数组
一提到数组,我第一时间经典的C语言实现和与之对应的一片定长连续的内存空间。数组的读写操作很快,时间复杂度为o(1),但是因其必须事先指定长度,所以空间利用率不高。数组的下标是数组中元素的标识,可以当做元素的身份证使用,在需要记录大量数据时,要利用好数组下标。
3 C语言细节
该节分3个部分介绍C语言从数组的必要语言细节。
3.1 数组越界问题
C语言不强制检查数组下标是否越界,使用时应时刻注意越界问题。
这个是一个毫无意义的问题,因为C语言根本不允许数组越界。
数组越界是一种Undefined behavior,C语言没规定程序运行结果,编译器也不保证这个结果。C语言规定这种错误编译器不必指出,所以编译可能会正常通过,但这依然是一种错误,且责任在CODER。
因此这是一个毫无意义的问题,就如同问袜子炖茄子会是什么味道。只有傻逼才会用袜子炖茄子然后亲自尝尝——这就是那个“解答”的本质。
作者:薛非
链接:https://www.zhihu.com/question/22897368/answer/22999166
来源:知乎
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。
3.2 数组与指针
本节介绍数组与指针之间的关系以及数组在使用中的注意点。
数组名是特殊的指针
本节介绍数组与指针的共同点和不同点。
以数组int a[10];
为例:
int a[10];
int n = 10;
int a[n]; //定义数组时,长度不可以为变量,该语句非法
共同点:通过指针访问数组元素
a[i]
与*(a+i)
、&a[i]
和a+i
都是等价的。- 通过等价指针访问数组
int *pa;
pa = &a[0]; //指针pa指向数组的0元素地址
pa = a; //这个写法和上句等价
x = *(pa+1);
x = a[1]; //这两句赋值语句等价
不同点:数组名与指针的区别
指针是一个变量,但是数组名不是变量。
int *pa;
pa = &a[0]; //指针pa是可以被赋值的,其指向地址可以改变
int b[10];
a = b; //a不可以被赋值,该语句非法
函数中传递的数组是指针(地址)
- 以《剑指offer》中的代码为例:
int GetSize(int data[])
{
return sizeof(data);
}
int main()
{
int data1[] ={1, 2, 3, 4, 5};
int size1 = sizeof(data1); //此处求数组data1所占字节数
int *data2 = data1;
int size2 = sizeof(data2); //此处求指针data2所占字节数
int size3 = GetSize(data1); //data1的地址被赋值给了局部变量data,所以返回指针data所占字节数
printf("%d, %d, %d", size1, size2, size3);
}
//输出结果为:20, 4, 4
- 传递部分数组
利用数组以指针形式传递的特性,我们可以数组的后本部分给函数。如f(&a[3])
和f(a+3)
,将数组a的后7个元素传递给了函数f。
3.3 数组与哈希表
数组可以看做一个简单的哈希表,其哈希函数为\(h(k)=k\),\(k\)为元素的关键字key。
常用的哈希函数有:
- 除法哈希法
\]
不太接近2的整数幂的素数适合作为\(m\)的值
2. 乘法哈希法
\]
其中\((kA mod 1)\)是取\(kA\)的小数部分,即\(kA- \lfloor kA \rfloor\)。
建议的变量取值为:\(m=2^p, p为大于0的整数\);\(A \approx (\sqrt 5 - 1)/2 \approx 0.618\)。
3. 全域哈希法
随机地选择哈希函数,使之独立于要存储的关键字。在此不做详细介绍。
4 编程题
在线编程资源
牛客网在线编程二维数组中的查找
Python:
# -*- coding:utf-8 -*-
class Solution:
# array 二维列表
def Find(self, target, array):
# write code here
r, c = len(array), len(array[0])
i, j = 0, c - 1 //选择合适的开始位置,右上角和左下角都可以
while (i < r and j >= 0):
if target < array[i][j]:
j = j - 1
elif target > array[i][j]:
i = i + 1
else:
return True
return False //之前将return放在while循环中,一直通不过
C语言:
C语言的实现和Python大同小异,牛客网的OJ系统貌似不支持C语言,此处略过。
5 结语
正如《黑客与画家》所说,编程语言是程序员的思考方式。思考问题的方式是在具体语言的基础上进行的,如数组,用C语言思考,我看到的是一片定长连续的内存空间;用Python思考,我看到是随意组合操作的不定长序列,学习不同的语言可以从不同的角度理解同一个概念,打破自己的思维局限。
最新文章
- Eclipse/JavaWeb (一)三大框架之struts框架 持续更新中...
- oracle+ibatis 批量插入-支持序列自增
- Sql Server之旅——第七站 为什么都说状态少的字段不能建索引
- 通过Web.config实现301重定向
- kvm虚拟机日常管理和配置操作命令梳理
- 使用MarkdonPad2学习心得
- 【codevs1257】 打砖块
- apidoc,一个相当不错的文档生成器
- 关于缺省路由传递问题的探讨(下)[ip default-network、ip default-gateway等]
- sublime_2014-11-19
- (转载)AS3领航系列教程 之 AS3程序的入口
- 关于table表格td里内容是数字而且太长不换行的问题
- jquary 单选,多选,select 获取和设置值 jquary自定义函数
- css设置多列等高布局
- 【原创】大数据基础之Quartz(1)简介、源代码解析
- iview导航菜单updateOpened和updateActiveName的使用
- uWSGI+Nginx安装、配置
- java.io.IOException: Server returned HTTP response code: 411 for URL
- [UGUI]Text文字效果
- MFC动态时间表示法——strtime函数
热门文章
- iOS 审核app被拒绝的各种理由以及翻译
- ifconfig-push
- 7.docker私有registry
- Textarea随着文本的字数自适应高度,后来发现用 contenteditable 代替textarea 效果更佳
- 从1G到5G,移动通信发展之路
- Nginx动静分离-tomcat
- 三维显示插件——C++
- 进阶3: zookeeper-3.4.9.tar.gz和hbase-1.2.4-bin.tar.gz 环境搭建(hbase 伪分布式)
- LR之流程
- linux 挂载磁盘指令