代码拉取完成，页面将自动刷新
<!DOCTYPE HTML>
<html lang="" >
<head>
<meta charset="UTF-8">
<meta content="text/html; charset=utf-8" http-equiv="Content-Type">
<title>算法 · GitBook</title>
<meta http-equiv="X-UA-Compatible" content="IE=edge" />
<meta name="description" content="">
<meta name="generator" content="GitBook 3.2.3">
<link rel="stylesheet" href="gitbook/style.css">
<link rel="stylesheet" href="gitbook/gitbook-plugin-highlight/website.css">
<link rel="stylesheet" href="gitbook/gitbook-plugin-search/search.css">
<link rel="stylesheet" href="gitbook/gitbook-plugin-fontsettings/website.css">
<meta name="HandheldFriendly" content="true"/>
<meta name="viewport" content="width=device-width, initial-scale=1, user-scalable=no">
<meta name="apple-mobile-web-app-capable" content="yes">
<meta name="apple-mobile-web-app-status-bar-style" content="black">
<link rel="apple-touch-icon-precomposed" sizes="152x152" href="gitbook/images/apple-touch-icon-precomposed-152.png">
<link rel="shortcut icon" href="gitbook/images/favicon.ico" type="image/x-icon">
<link rel="next" href="Foundation.html" />
<link rel="prev" href="Data-structure.html" />
</head>
<body>
<div class="book">
<div class="book-summary">
<div id="book-search-input" role="search">
<input type="text" placeholder="Type to search" />
</div>
<nav role="navigation">
<ul class="summary">
<li class="chapter " data-level="1.1" data-path="./">
<a href="./">
关于
</a>
</li>
<li class="header">Part I</li>
<li class="chapter " data-level="2.1" data-path="Data-structure.html">
<a href="Data-structure.html">
数据结构
</a>
</li>
<li class="chapter active" data-level="2.2" data-path="Arithmetic.html">
<a href="Arithmetic.html">
算法
</a>
</li>
<li class="header">Part II</li>
<li class="chapter " data-level="3.1" data-path="Foundation.html">
<a href="Foundation.html">
Foundation
</a>
</li>
<li class="chapter " data-level="3.2" data-path="UIKit.html">
<a href="UIKit.html">
UIKit
</a>
</li>
<li class="chapter " data-level="3.3" data-path="WebView.html">
<a href="WebView.html">
WebView
</a>
</li>
<li class="chapter " data-level="3.4" data-path="Memory-management.html">
<a href="Memory-management.html">
内存管理
</a>
</li>
<li class="chapter " data-level="3.5" data-path="Message-passing.html">
<a href="Message-passing.html">
消息传递的方式
</a>
</li>
<li class="chapter " data-level="3.6" data-path="Network.html">
<a href="Network.html">
网络
</a>
</li>
<li class="chapter " data-level="3.7" data-path="Data-storage.html">
<a href="Data-storage.html">
数据存储
</a>
</li>
<li class="chapter " data-level="3.8" data-path="Multi-thread.html">
<a href="Multi-thread.html">
多线程
</a>
</li>
<li class="chapter " data-level="3.9" data-path="Animation.html">
<a href="Animation.html">
动画
</a>
</li>
<li class="chapter " data-level="3.10" data-path="Image-processing.html">
<a href="Image-processing.html">
图像处理
</a>
</li>
<li class="chapter " data-level="3.11" data-path="Data-encryption.html">
<a href="Data-encryption.html">
数据安全及加密
</a>
</li>
<li class="chapter " data-level="3.12" data-path="Runtime.html">
<a href="Runtime.html">
Runtime
</a>
</li>
<li class="chapter " data-level="3.13" data-path="Runloop.html">
<a href="Runloop.html">
Runloop
</a>
</li>
<li class="header">Part III</li>
<li class="chapter " data-level="4.1" data-path="Project-organization.html">
<a href="Project-organization.html">
项目架构
</a>
</li>
<li class="chapter " data-level="4.2" data-path="Design-patterns.html">
<a href="Design-patterns.html">
设计模式
</a>
</li>
<li class="chapter " data-level="4.3" data-path="Component-based.html">
<a href="Component-based.html">
组件化
</a>
</li>
<li class="chapter " data-level="4.4" data-path="Debug-tips.html">
<a href="Debug-tips.html">
调试技巧
</a>
</li>
<li class="chapter " data-level="4.5" data-path="Performance-optimization.html">
<a href="Performance-optimization.html">
性能优化
</a>
</li>
<li class="chapter " data-level="4.6" data-path="Source-code.html">
<a href="Source-code.html">
源码理解
</a>
</li>
<li class="chapter " data-level="4.7" data-path="Code-management.html">
<a href="Code-management.html">
代码管理
</a>
</li>
<li class="chapter " data-level="4.8" data-path="Continuous-integration.html">
<a href="Continuous-integration.html">
持续集成
</a>
</li>
<li class="divider"></li>
<li>
<a href="https://www.gitbook.com" target="blank" class="gitbook-link">
Published with GitBook
</a>
</li>
</ul>
</nav>
</div>
<div class="book-body">
<div class="body-inner">
<div class="book-header" role="navigation">
<!-- Title -->
<h1>
<i class="fa fa-circle-o-notch fa-spin"></i>
<a href="." >算法</a>
</h1>
</div>
<div class="page-wrapper" tabindex="-1" role="main">
<div class="page-inner">
<div id="book-search-results">
<div class="search-noresults">
<section class="normal markdown-section">
<h1 id="算法">算法</h1>
<h2 id="1时间复杂度">1.时间复杂度</h2>
<ul>
<li><p>时间频度</p>
<p> 一个算法执行所耗费的时间,从理论上是不能算出来的,必须上机运行测试才能知道.但我们不可能也没有必要对每个算法都上机测试,只需知道哪个算法花费的时间多,哪个算法花费的时间少就可以了.并且一个算法花费的时间与算法中语句的执行次数成正比例,哪个算法中语句执行次数多,它花费时间就多.一个算法中的语句执行次数称为语句频度或时间频度.记为T(n).</p>
</li>
<li><p>时间复杂度</p>
<p> 一般情况下,算法中基本操作重复执行的次数是问题规模n的某个函数,用T(n)表示,若有某个辅助函数f(n),使得当n趋近于无穷大时,T（n)/f(n)的极限值为不等于零的常数,则称f(n)是T(n)的同数量级函数.记作T(n)=O(f(n)),称O(f(n)) 为算法的渐进时间复杂度,简称时间复杂度.</p>
</li>
<li><p>在各种不同算法中,若算法中语句执行次数为一个常数,则时间复杂度为O(1),另外,在时间频度不相同时,时间复杂度有可能相同,如T(n)=n2+3n+4与T(n)=4n2+2n+1它们的频度不同,但时间复杂度相同,都为O(n2).</p>
</li>
<li><p>按数量级递增排列,常见的时间复杂度有：</p>
<p> O(1)称为常量级，算法的时间复杂度是一个常数。</p>
<p> O(n)称为线性级，时间复杂度是数据量n的线性函数。</p>
<p> O(n²)称为平方级，与数据量n的二次多项式函数属于同一数量级。</p>
<p> O(n³)称为立方级，是n的三次多项式函数。</p>
<p> O(logn)称为对数级，是n的对数函数。</p>
<p> O(nlogn)称为介于线性级和平方级之间的一种数量级</p>
<p> O(2ⁿ)称为指数级，与数据量n的指数函数是一个数量级。</p>
<p> O(n!)称为阶乘级，与数据量n的阶乘是一个数量级。</p>
<p> 它们之间的关系是： O(1)<O(logn)<O(n)<O(nlogn)<O(n²)<O(n³)<O(2ⁿ)<O(n!)，随着问题规模n的不断增大,上述时间复杂度不断增大,算法的执行效率越低.</p>
</li>
</ul>
<h2 id="2空间复杂度">2.空间复杂度</h2>
<ul>
<li>评估执行程序所需的存储空间。可以估算出程序对计算机内存的使用程度。不包括算法程序代码和所处理的数据本身所占空间部分。通常用所使用额外空间的字节数表示。其算法比较简单，记为S(n)=O(f(n))，其中，n表示问题规模。</li>
</ul>
<h2 id="3常用的排序算法">3.常用的排序算法</h2>
<ul>
<li><p>选择排序、冒泡排序、插入排序三种排序算法可以总结为如下：</p>
<p> 都将数组分为已排序部分和未排序部分。</p>
<p> 选择排序将已排序部分定义在左端，然后选择未排序部分的最小元素和未排序部分的第一个元素交换。</p>
<p> 冒泡排序将已排序部分定义在右端，在遍历未排序部分的过程执行交换，将最大元素交换到最右端。</p>
<p> 插入排序将已排序部分定义在左端，将未排序部分元的第一个元素插入到已排序部分合适的位置。</p>
</li>
</ul>
<pre><code class="lang-c"><span class="hljs-comment">/**
* 【选择排序】：最值出现在起始端
*
* 第1趟：在n个数中找到最小(大)数与第一个数交换位置
* 第2趟：在剩下n-1个数中找到最小(大)数与第二个数交换位置
* 重复这样的操作...依次与第三个、第四个...数交换位置
* 第n-1趟，最终可实现数据的升序（降序）排列。
*
*/</span>
<span class="hljs-function"><span class="hljs-keyword">void</span> <span class="hljs-title">selectSort</span><span class="hljs-params">(<span class="hljs-keyword">int</span> *arr, <span class="hljs-keyword">int</span> length)</span> </span>{
<span class="hljs-keyword">for</span> (<span class="hljs-keyword">int</span> i = <span class="hljs-number">0</span>; i < length - <span class="hljs-number">1</span>; i++) { <span class="hljs-comment">//趟数</span>
<span class="hljs-keyword">for</span> (<span class="hljs-keyword">int</span> j = i + <span class="hljs-number">1</span>; j < length; j++) { <span class="hljs-comment">//比较次数</span>
<span class="hljs-keyword">if</span> (arr[i] > arr[j]) {
<span class="hljs-keyword">int</span> temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
}
}
<span class="hljs-comment">/**
* 【冒泡排序】：相邻元素两两比较，比较完一趟，最值出现在末尾
* 第1趟：依次比较相邻的两个数，不断交换（小数放前，大数放后）逐个推进，最值最后出现在第n个元素位置
* 第2趟：依次比较相邻的两个数，不断交换（小数放前，大数放后）逐个推进，最值最后出现在第n-1个元素位置
* …… ……
* 第n-1趟：依次比较相邻的两个数，不断交换（小数放前，大数放后）逐个推进，最值最后出现在第2个元素位置
*/</span>
<span class="hljs-function"><span class="hljs-keyword">void</span> <span class="hljs-title">bublleSort</span><span class="hljs-params">(<span class="hljs-keyword">int</span> *arr, <span class="hljs-keyword">int</span> length)</span> </span>{
<span class="hljs-keyword">for</span>(<span class="hljs-keyword">int</span> i = <span class="hljs-number">0</span>; i < length - <span class="hljs-number">1</span>; i++) { <span class="hljs-comment">//趟数</span>
<span class="hljs-keyword">for</span>(<span class="hljs-keyword">int</span> j = <span class="hljs-number">0</span>; j < length - i - <span class="hljs-number">1</span>; j++) { <span class="hljs-comment">//比较次数</span>
<span class="hljs-keyword">if</span>(arr[j] > arr[j+<span class="hljs-number">1</span>]) {
<span class="hljs-keyword">int</span> temp = arr[j];
arr[j] = arr[j+<span class="hljs-number">1</span>];
arr[j+<span class="hljs-number">1</span>] = temp;
}
}
}
}
<span class="hljs-comment">/**
* 折半查找：优化查找时间（不用遍历全部数据）
*
* 折半查找的原理：
* 1> 数组必须是有序的
* 2> 必须已知min和max（知道范围）
* 3> 动态计算mid的值，取出mid对应的值进行比较
* 4> 如果mid对应的值大于要查找的值，那么max要变小为mid-1
* 5> 如果mid对应的值小于要查找的值，那么min要变大为mid+1
*
*/</span>
<span class="hljs-comment">// 已知一个有序数组, 和一个key, 要求从数组中找到key对应的索引位置 </span>
<span class="hljs-function"><span class="hljs-keyword">int</span> <span class="hljs-title">findKey</span><span class="hljs-params">(<span class="hljs-keyword">int</span> *arr, <span class="hljs-keyword">int</span> length, <span class="hljs-keyword">int</span> key)</span> </span>{
<span class="hljs-keyword">int</span> min = <span class="hljs-number">0</span>, max = length - <span class="hljs-number">1</span>, mid;
<span class="hljs-keyword">while</span> (min <= max) {
mid = (min + max) / <span class="hljs-number">2</span>; <span class="hljs-comment">//计算中间值</span>
<span class="hljs-keyword">if</span> (key > arr[mid]) {
min = mid + <span class="hljs-number">1</span>;
} <span class="hljs-keyword">else</span> <span class="hljs-keyword">if</span> (key < arr[mid]) {
max = mid - <span class="hljs-number">1</span>;
} <span class="hljs-keyword">else</span> {
<span class="hljs-keyword">return</span> mid;
}
}
<span class="hljs-keyword">return</span> <span class="hljs-number">-1</span>;
}
</code></pre>
<h2 id="4字符串反转">4.字符串反转</h2>
<pre><code class="lang-c"><span class="hljs-function"><span class="hljs-keyword">void</span> <span class="hljs-title">char_reverse</span> <span class="hljs-params">(<span class="hljs-keyword">char</span> *cha)</span> </span>{
<span class="hljs-comment">// 定义头部指针</span>
<span class="hljs-keyword">char</span> *begin = cha;
<span class="hljs-comment">// 定义尾部指针</span>
<span class="hljs-keyword">char</span> *end = cha + <span class="hljs-built_in">strlen</span>(cha) <span class="hljs-number">-1</span>;
<span class="hljs-keyword">while</span> (begin < end) {
<span class="hljs-keyword">char</span> temp = *begin;
*(begin++) = *end;
*(end--) = temp;
}
}
</code></pre>
<h2 id="5链表反转（头差法）">5.链表反转（头差法）</h2>
<p>.h声明文件</p>
<pre><code class="lang-c"><span class="hljs-meta">#import <Foundation/Foundation.h></span>
<span class="hljs-comment">// 定义一个链表</span>
<span class="hljs-keyword">struct</span> Node {
<span class="hljs-keyword">int</span> data;
<span class="hljs-keyword">struct</span> Node *next;
};
@interface ReverseList : NSObject
<span class="hljs-comment">// 链表反转</span>
<span class="hljs-function"><span class="hljs-keyword">struct</span> Node* <span class="hljs-title">reverseList</span><span class="hljs-params">(<span class="hljs-keyword">struct</span> Node *head)</span></span>;
<span class="hljs-comment">// 构造一个链表</span>
<span class="hljs-function"><span class="hljs-keyword">struct</span> Node* <span class="hljs-title">constructList</span><span class="hljs-params">(<span class="hljs-keyword">void</span>)</span></span>;
<span class="hljs-comment">// 打印链表中的数据</span>
<span class="hljs-function"><span class="hljs-keyword">void</span> <span class="hljs-title">printList</span><span class="hljs-params">(<span class="hljs-keyword">struct</span> Node *head)</span></span>;
@end
</code></pre>
<p>.m实现文件</p>
<pre><code class="lang-c"><span class="hljs-meta">#import <span class="hljs-string">"ReverseList.h"</span></span>
@<span class="hljs-function">implementation ReverseList
<span class="hljs-keyword">struct</span> Node* <span class="hljs-title">reverseList</span><span class="hljs-params">(<span class="hljs-keyword">struct</span> Node *head)</span>
</span>{
<span class="hljs-comment">// 定义遍历指针，初始化为头结点</span>
<span class="hljs-keyword">struct</span> Node *p = head;
<span class="hljs-comment">// 反转后的链表头部</span>
<span class="hljs-keyword">struct</span> Node *newH = <span class="hljs-literal">NULL</span>;
<span class="hljs-comment">// 遍历链表</span>
<span class="hljs-keyword">while</span> (p != <span class="hljs-literal">NULL</span>) {
<span class="hljs-comment">// 记录下一个结点</span>
<span class="hljs-keyword">struct</span> Node *temp = p->next;
<span class="hljs-comment">// 当前结点的next指向新链表头部</span>
p->next = newH;
<span class="hljs-comment">// 更改新链表头部为当前结点</span>
newH = p;
<span class="hljs-comment">// 移动p指针</span>
p = temp;
}
<span class="hljs-comment">// 返回反转后的链表头结点</span>
<span class="hljs-keyword">return</span> newH;
}
<span class="hljs-function"><span class="hljs-keyword">struct</span> Node* <span class="hljs-title">constructList</span><span class="hljs-params">(<span class="hljs-keyword">void</span>)</span>
</span>{
<span class="hljs-comment">// 头结点定义</span>
<span class="hljs-keyword">struct</span> Node *head = <span class="hljs-literal">NULL</span>;
<span class="hljs-comment">// 记录当前尾结点</span>
<span class="hljs-keyword">struct</span> Node *cur = <span class="hljs-literal">NULL</span>;
<span class="hljs-keyword">for</span> (<span class="hljs-keyword">int</span> i = <span class="hljs-number">1</span>; i < <span class="hljs-number">5</span>; i++) {
<span class="hljs-keyword">struct</span> Node *node = <span class="hljs-built_in">malloc</span>(<span class="hljs-keyword">sizeof</span>(<span class="hljs-keyword">struct</span> Node));
node->data = i;
<span class="hljs-comment">// 头结点为空，新结点即为头结点</span>
<span class="hljs-keyword">if</span> (head == <span class="hljs-literal">NULL</span>) {
head = node;
}
<span class="hljs-comment">// 当前结点的next为新结点</span>
<span class="hljs-keyword">else</span>{
cur->next = node;
}
<span class="hljs-comment">// 设置当前结点为新结点</span>
cur = node;
}
<span class="hljs-keyword">return</span> head;
}
<span class="hljs-function"><span class="hljs-keyword">void</span> <span class="hljs-title">printList</span><span class="hljs-params">(<span class="hljs-keyword">struct</span> Node *head)</span>
</span>{
<span class="hljs-keyword">struct</span> Node* temp = head;
<span class="hljs-keyword">while</span> (temp != <span class="hljs-literal">NULL</span>) {
<span class="hljs-built_in">printf</span>(<span class="hljs-string">"node is %d \n"</span>, temp->data);
temp = temp->next;
}
}
@end
</code></pre>
<h2 id="6有序数组合并">6.有序数组合并</h2>
<p>.h声明文件</p>
<pre><code class="lang-c"><span class="hljs-meta">#import <Foundation/Foundation.h></span>
@interface MergeSortedList : NSObject
<span class="hljs-comment">// 将有序数组a和b的值合并到一个数组result当中，且仍然保持有序</span>
<span class="hljs-function"><span class="hljs-keyword">void</span> <span class="hljs-title">mergeList</span><span class="hljs-params">(<span class="hljs-keyword">int</span> a[], <span class="hljs-keyword">int</span> aLen, <span class="hljs-keyword">int</span> b[], <span class="hljs-keyword">int</span> bLen, <span class="hljs-keyword">int</span> result[])</span></span>;
@end
</code></pre>
<p>.m实现文件</p>
<pre><code class="lang-c"><span class="hljs-meta">#import <span class="hljs-string">"MergeSortedList.h"</span></span>
@<span class="hljs-function">implementation MergeSortedList
<span class="hljs-keyword">void</span> <span class="hljs-title">mergeList</span><span class="hljs-params">(<span class="hljs-keyword">int</span> a[], <span class="hljs-keyword">int</span> aLen, <span class="hljs-keyword">int</span> b[], <span class="hljs-keyword">int</span> bLen, <span class="hljs-keyword">int</span> result[])</span>
</span>{
<span class="hljs-keyword">int</span> p = <span class="hljs-number">0</span>; <span class="hljs-comment">// 遍历数组a的指针</span>
<span class="hljs-keyword">int</span> q = <span class="hljs-number">0</span>; <span class="hljs-comment">// 遍历数组b的指针</span>
<span class="hljs-keyword">int</span> i = <span class="hljs-number">0</span>; <span class="hljs-comment">// 记录当前存储位置</span>
<span class="hljs-comment">// 任一数组没有到达边界则进行遍历</span>
<span class="hljs-keyword">while</span> (p < aLen && q < bLen) {
<span class="hljs-comment">// 如果a数组对应位置的值小于b数组对应位置的值</span>
<span class="hljs-keyword">if</span> (a[p] <= b[q]) {
<span class="hljs-comment">// 存储a数组的值</span>
result[i] = a[p];
<span class="hljs-comment">// 移动a数组的遍历指针</span>
p++;
}
<span class="hljs-keyword">else</span>{
<span class="hljs-comment">// 存储b数组的值</span>
result[i] = b[q];
<span class="hljs-comment">// 移动b数组的遍历指针</span>
q++;
}
<span class="hljs-comment">// 指向合并结果的下一个存储位置</span>
i++;
}
<span class="hljs-comment">// 如果a数组有剩余</span>
<span class="hljs-keyword">while</span> (p < aLen) {
<span class="hljs-comment">// 将a数组剩余部分拼接到合并结果的后面</span>
result[i] = a[p++];
i++;
}
<span class="hljs-comment">// 如果b数组有剩余</span>
<span class="hljs-keyword">while</span> (q < bLen) {
<span class="hljs-comment">// 将b数组剩余部分拼接到合并结果的后面</span>
result[i] = b[q++];
i++;
}
}
@end
</code></pre>
<h2 id="7查找第一个只出现一次的字符（hash查找）">7.查找第一个只出现一次的字符（Hash查找）</h2>
<p>.h声明文件</p>
<pre><code class="lang-c"><span class="hljs-meta">#import <Foundation/Foundation.h></span>
@interface HashFind : NSObject
<span class="hljs-comment">// 查找第一个只出现一次的字符</span>
<span class="hljs-function"><span class="hljs-keyword">char</span> <span class="hljs-title">findFirstChar</span><span class="hljs-params">(<span class="hljs-keyword">char</span>* cha)</span></span>;
@end
</code></pre>
<p>.m实现文件</p>
<pre><code class="lang-c"><span class="hljs-meta">#import <span class="hljs-string">"HashFind.h"</span></span>
@<span class="hljs-function">implementation HashFind
<span class="hljs-keyword">char</span> <span class="hljs-title">findFirstChar</span><span class="hljs-params">(<span class="hljs-keyword">char</span>* cha)</span>
</span>{
<span class="hljs-keyword">char</span> result = <span class="hljs-string">'\0'</span>;
<span class="hljs-comment">// 定义一个数组 用来存储各个字母出现次数</span>
<span class="hljs-keyword">int</span> <span class="hljs-built_in">array</span>[<span class="hljs-number">256</span>];
<span class="hljs-comment">// 对数组进行初始化操作</span>
<span class="hljs-keyword">for</span> (<span class="hljs-keyword">int</span> i=<span class="hljs-number">0</span>; i<<span class="hljs-number">256</span>; i++) {
<span class="hljs-built_in">array</span>[i] =<span class="hljs-number">0</span>;
}
<span class="hljs-comment">// 定义一个指针 指向当前字符串头部</span>
<span class="hljs-keyword">char</span>* p = cha;
<span class="hljs-comment">// 遍历每个字符</span>
<span class="hljs-keyword">while</span> (*p != <span class="hljs-string">'\0'</span>) {
<span class="hljs-comment">// 在字母对应存储位置 进行出现次数+1操作</span>
<span class="hljs-built_in">array</span>[*(p++)]++;
}
<span class="hljs-comment">// 将P指针重新指向字符串头部</span>
p = cha;
<span class="hljs-comment">// 遍历每个字母的出现次数</span>
<span class="hljs-keyword">while</span> (*p != <span class="hljs-string">'\0'</span>) {
<span class="hljs-comment">// 遇到第一个出现次数为1的字符，打印结果</span>
<span class="hljs-keyword">if</span> (<span class="hljs-built_in">array</span>[*p] == <span class="hljs-number">1</span>)
{
result = *p;
<span class="hljs-keyword">break</span>;
}
<span class="hljs-comment">// 反之继续向后遍历</span>
p++;
}
<span class="hljs-keyword">return</span> result;
}
@end
</code></pre>
<h2 id="8查找两个子视图的共同父视图">8.查找两个子视图的共同父视图</h2>
<p>.h声明文件</p>
<pre><code class="lang-c"><span class="hljs-meta">#import <Foundation/Foundation.h></span>
<span class="hljs-meta">#import <UIKit/UIKit.h></span>
@interface CommonSuperFind : NSObject
<span class="hljs-comment">// 查找两个视图的共同父视图</span>
- (NSArray<UIView *> *)findCommonSuperView:(UIView *)view other:(UIView *)viewOther;
@end
</code></pre>
<p>.m实现文件</p>
<pre><code class="lang-c"><span class="hljs-meta">#import <span class="hljs-string">"CommonSuperFind.h"</span></span>
@implementation CommonSuperFind
- (NSArray <UIView *> *)findCommonSuperView:(UIView *)viewOne other:(UIView *)viewOther
{
NSMutableArray *result = [NSMutableArray <span class="hljs-built_in">array</span>];
<span class="hljs-comment">// 查找第一个视图的所有父视图</span>
NSArray *arrayOne = [self findSuperViews:viewOne];
<span class="hljs-comment">// 查找第二个视图的所有父视图</span>
NSArray *arrayOther = [self findSuperViews:viewOther];
<span class="hljs-keyword">int</span> i = <span class="hljs-number">0</span>;
<span class="hljs-comment">// 越界限制条件</span>
<span class="hljs-keyword">while</span> (i < MIN((<span class="hljs-keyword">int</span>)arrayOne.count, (<span class="hljs-keyword">int</span>)arrayOther.count)) {
<span class="hljs-comment">// 倒序方式获取各个视图的父视图</span>
UIView *superOne = [arrayOne objectAtIndex:arrayOne.count - i - <span class="hljs-number">1</span>];
UIView *superOther = [arrayOther objectAtIndex:arrayOther.count - i - <span class="hljs-number">1</span>];
<span class="hljs-comment">// 比较如果相等 则为共同父视图</span>
<span class="hljs-keyword">if</span> (superOne == superOther) {
[result addObject:superOne];
i++;
}
<span class="hljs-comment">// 如果不相等，则结束遍历</span>
<span class="hljs-keyword">else</span>{
<span class="hljs-keyword">break</span>;
}
}
<span class="hljs-keyword">return</span> result;
}
- (NSArray <UIView *> *)findSuperViews:(UIView *)view
{
<span class="hljs-comment">// 初始化为第一父视图</span>
UIView *temp = view.superview;
<span class="hljs-comment">// 保存结果的数组</span>
NSMutableArray *result = [NSMutableArray <span class="hljs-built_in">array</span>];
<span class="hljs-keyword">while</span> (temp) {
[result addObject:temp];
<span class="hljs-comment">// 顺着superview指针一直向上查找</span>
temp = temp.superview;
}
<span class="hljs-keyword">return</span> result;
}
@end
</code></pre>
<h2 id="9无序数组中的中位数快排思想">9.无序数组中的中位数(快排思想)</h2>
<p>.h声明文件</p>
<pre><code class="lang-c"><span class="hljs-meta">#import <Foundation/Foundation.h></span>
@interface MedianFind : NSObject
<span class="hljs-comment">// 无序数组中位数查找</span>
<span class="hljs-function"><span class="hljs-keyword">int</span> <span class="hljs-title">findMedian</span><span class="hljs-params">(<span class="hljs-keyword">int</span> a[], <span class="hljs-keyword">int</span> aLen)</span></span>;
@end
</code></pre>
<pre><code class="lang-c">.m实现文件
<span class="hljs-meta">#import <span class="hljs-string">"MedianFind.h"</span></span>
@implementation MedianFind
<span class="hljs-comment">//求一个无序数组的中位数</span>
<span class="hljs-function"><span class="hljs-keyword">int</span> <span class="hljs-title">findMedian</span><span class="hljs-params">(<span class="hljs-keyword">int</span> a[], <span class="hljs-keyword">int</span> aLen)</span>
</span>{
<span class="hljs-keyword">int</span> low = <span class="hljs-number">0</span>;
<span class="hljs-keyword">int</span> high = aLen - <span class="hljs-number">1</span>;
<span class="hljs-keyword">int</span> mid = (aLen - <span class="hljs-number">1</span>) / <span class="hljs-number">2</span>;
<span class="hljs-keyword">int</span> div = PartSort(a, low, high);
<span class="hljs-keyword">while</span> (div != mid)
{
<span class="hljs-keyword">if</span> (mid < div)
{
<span class="hljs-comment">//左半区间找</span>
div = PartSort(a, low, div - <span class="hljs-number">1</span>);
}
<span class="hljs-keyword">else</span>
{
<span class="hljs-comment">//右半区间找</span>
div = PartSort(a, div + <span class="hljs-number">1</span>, high);
}
}
<span class="hljs-comment">//找到了</span>
<span class="hljs-keyword">return</span> a[mid];
}
<span class="hljs-function"><span class="hljs-keyword">int</span> <span class="hljs-title">PartSort</span><span class="hljs-params">(<span class="hljs-keyword">int</span> a[], <span class="hljs-keyword">int</span> start, <span class="hljs-keyword">int</span> end)</span>
</span>{
<span class="hljs-keyword">int</span> low = start;
<span class="hljs-keyword">int</span> high = end;
<span class="hljs-comment">//选取关键字</span>
<span class="hljs-keyword">int</span> key = a[end];
<span class="hljs-keyword">while</span> (low < high)
{
<span class="hljs-comment">//左边找比key大的值</span>
<span class="hljs-keyword">while</span> (low < high && a[low] <= key)
{
++low;
}
<span class="hljs-comment">//右边找比key小的值</span>
<span class="hljs-keyword">while</span> (low < high && a[high] >= key)
{
--high;
}
<span class="hljs-keyword">if</span> (low < high)
{
<span class="hljs-comment">//找到之后交换左右的值</span>
<span class="hljs-keyword">int</span> temp = a[low];
a[low] = a[high];
a[high] = temp;
}
}
<span class="hljs-keyword">int</span> temp = a[high];
a[high] = a[end];
a[end] = temp;
<span class="hljs-keyword">return</span> low;
}
@end
</code></pre>
<h2 id="10给定一个整数数组和一个目标值，找出数组中和为目标值的两个数。">10.给定一个整数数组和一个目标值，找出数组中和为目标值的两个数。</h2>
<pre><code class="lang-c">- (<span class="hljs-keyword">void</span>)viewDidLoad {
[super viewDidLoad];
NSArray *oriArray = @[@(<span class="hljs-number">2</span>),@(<span class="hljs-number">3</span>),@(<span class="hljs-number">6</span>),@(<span class="hljs-number">7</span>),@(<span class="hljs-number">22</span>),@(<span class="hljs-number">12</span>)];
BOOL isHaveNums = [self twoNumSumWithTarget:<span class="hljs-number">9</span> Array:oriArray];
NSLog(@<span class="hljs-string">"%d"</span>,isHaveNums);
}
- (BOOL)twoNumSumWithTarget:(<span class="hljs-keyword">int</span>)target Array:(NSArray<NSNumber *> *)<span class="hljs-built_in">array</span> {
NSMutableArray *finalArray = [NSMutableArray <span class="hljs-built_in">array</span>];
<span class="hljs-keyword">for</span> (<span class="hljs-keyword">int</span> i = <span class="hljs-number">0</span>; i < <span class="hljs-built_in">array</span>.count; i++) {
<span class="hljs-keyword">for</span> (<span class="hljs-keyword">int</span> j = i + <span class="hljs-number">1</span>; j < <span class="hljs-built_in">array</span>.count; j++) {
<span class="hljs-keyword">if</span> ([<span class="hljs-built_in">array</span>[i] intValue] + [<span class="hljs-built_in">array</span>[j] intValue] == target) {
[finalArray addObject:<span class="hljs-built_in">array</span>[i]];
[finalArray addObject:<span class="hljs-built_in">array</span>[j]];
NSLog(@<span class="hljs-string">"%@"</span>,finalArray);
<span class="hljs-keyword">return</span> YES;
}
}
}
<span class="hljs-keyword">return</span> NO;
}
</code></pre>
</section>
</div>
<div class="search-results">
<div class="has-results">
<h1 class="search-results-title"><span class='search-results-count'></span> results matching "<span class='search-query'></span>"</h1>
<ul class="search-results-list"></ul>
</div>
<div class="no-results">
<h1 class="search-results-title">No results matching "<span class='search-query'></span>"</h1>
</div>
</div>
</div>
</div>
</div>
</div>
<a href="Data-structure.html" class="navigation navigation-prev " aria-label="Previous page: 数据结构">
<i class="fa fa-angle-left"></i>
</a>
<a href="Foundation.html" class="navigation navigation-next " aria-label="Next page: Foundation">
<i class="fa fa-angle-right"></i>
</a>
</div>
<script>
var gitbook = gitbook || [];
gitbook.push(function() {
gitbook.page.hasChanged({"page":{"title":"算法","level":"2.2","depth":1,"next":{"title":"Foundation","level":"3.1","depth":1,"path":"Foundation.md","ref":"Foundation.md","articles":[]},"previous":{"title":"数据结构","level":"2.1","depth":1,"path":"Data-structure.md","ref":"Data-structure.md","articles":[]},"dir":"ltr"},"config":{"gitbook":"*","theme":"default","variables":{},"plugins":["livereload"],"pluginsConfig":{"livereload":{},"highlight":{},"search":{},"lunr":{"maxIndexSize":1000000,"ignoreSpecialCharacters":false},"sharing":{"facebook":true,"twitter":true,"google":false,"weibo":false,"instapaper":false,"vk":false,"all":["facebook","google","twitter","weibo","instapaper"]},"fontsettings":{"theme":"white","family":"sans","size":2},"theme-default":{"styles":{"website":"styles/website.css","pdf":"styles/pdf.css","epub":"styles/epub.css","mobi":"styles/mobi.css","ebook":"styles/ebook.css","print":"styles/print.css"},"showLevel":false}},"structure":{"langs":"LANGS.md","readme":"README.md","glossary":"GLOSSARY.md","summary":"SUMMARY.md"},"pdf":{"pageNumbers":true,"fontSize":12,"fontFamily":"Arial","paperSize":"a4","chapterMark":"pagebreak","pageBreaksBefore":"/","margin":{"right":62,"left":62,"top":56,"bottom":56}},"styles":{"website":"styles/website.css","pdf":"styles/pdf.css","epub":"styles/epub.css","mobi":"styles/mobi.css","ebook":"styles/ebook.css","print":"styles/print.css"}},"file":{"path":"Arithmetic.md","mtime":"2020-04-13T10:23:32.000Z","type":"markdown"},"gitbook":{"version":"3.2.3","time":"2020-05-27T09:12:21.691Z"},"basePath":".","book":{"language":""}});
});
</script>
</div>
<script src="gitbook/gitbook.js"></script>
<script src="gitbook/theme.js"></script>
<script src="gitbook/gitbook-plugin-livereload/plugin.js"></script>
<script src="gitbook/gitbook-plugin-search/search-engine.js"></script>
<script src="gitbook/gitbook-plugin-search/search.js"></script>
<script src="gitbook/gitbook-plugin-lunr/lunr.min.js"></script>
<script src="gitbook/gitbook-plugin-lunr/search-lunr.js"></script>
<script src="gitbook/gitbook-plugin-sharing/buttons.js"></script>
<script src="gitbook/gitbook-plugin-fontsettings/fontsettings.js"></script>
</body>
</html>
此处可能存在不合适展示的内容，页面不予展示。您可通过相关编辑功能自查并修改。
如您确认内容无涉及 不当用语 / 纯广告导流 / 暴力 / 低俗色情 / 侵权 / 盗版 / 虚假 / 无价值内容或违法国家有关法律法规的内容，可点击提交进行申诉，我们将尽快为您处理。
