数组中的算法

目次
1.什么是数组
2.数组上的算法
2.1二分查找算法
什么是二分查找算法？
算法步骤
算法时间复杂度
一个题目
例题
标题分析
解题代码   
2.2双指针法
什么是双指针法？
例题
标题分析
解题代码

---

1.什么是数组

数组是在一块连续的内存空间上存储相同范例数据的集合。实在数组也是一种基本的数据结构，也是许多更加高级的数结构的底子，好比 栈、队列、哈希表……都可以基于数组实现。
下图展示了一个长度为12的 int 范例的数组：

需要注意的是： 

• 数组的下标是从0开始计数的。
  
• 数组在内存空间中的地点是连续的。
  

2.数组上的算法

由于数组的要求是一块连续的内存空间，所以我们可以利用其连续的特性玩一些算法。
2.1二分查找算法

什么是二分查找算法？

二分查找算法（Binary Search Algorithm）是一种在有序数组中查找某一特定元素的搜刮算法。
算法步骤

• 定义左右两个指针。（这里的指针是形象的说法，代表数字的下标）
  
• 盘算出中间元素的下标，判断待查找元素与数组中间元素的巨细。
  
• 假如该特定元素小于中间元素，则在中间元素的左边的区间举行查找；需要更新右指针的值。
  
• 假如该特定元素大于中间元素，则在中间元素的右边的区间举行查找；需要更新左指针的值。
  

算法时间复杂度

这种搜刮算法每一次比较都使搜刮范围缩小一半，因此其时间复杂度为O(log n)，此中n是数组的长度。
一个题目

整个查找过程在一个循环中举行，在未找到指定元素的情况下，左指针不断向右移，右指针不断向左移，那么循环的竣事条件是什么呢？是left < right 还是 left <= right 呢？
怎么写这个循环的竣事条件，重要取决于left == right 的情况是否故意义，故意义就写成 <= ，没故意义就写成 < ；那么 left == right 到底有没故意义，重要取决于right指针的定义，right指针的定义决定了待查找的区间是 左闭右闭 还是 左闭右开 的。

例题

标题链接 —— 二分查找  (标题来源于力扣)
   标题：给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target  ，写一个函数搜刮 nums 中的 target，假如目标值存在返回下标，否则返回 -1。
  标题分析

标题表明给定的数组是有序的，而且是升序，也就是说数组中没有重复的元素，因此查找到的下标是唯一的，我们可以考虑利用二分查找算法。
解题代码   

写法一：定义左闭右闭区间。当我们定义区间为左闭右闭时，left == right 这种情况是有效的。

1. // 定义左闭右闭
2. class Solution {
3. public:
4.     int search(vector<int>& nums, int target) {
5.         int left = 0;
6.         int right = nums.size()-1;
8.         while(left <= right) //left == right 有意义
9.         {
10.             int mid = left + (right-left)/2; // 防止溢出
12.             if(nums[mid] > target)
13.             {
14.                 right = mid-1;
15.             }
16.             else if(nums[mid] < target)
17.             {
18.                 left = mid+1;
19.             }
20.             else
21.             {
22.                 return mid;
23.             }
24.         }
26.         return -1;
27.     }
28. };

复制代码

写法二：定义左闭右开区间。当我们定义左闭右开区间时，left == right 这种情况是没故意义的。

1. // 定义左闭右开
2. class Solution {
3. public:
4.     int search(vector<int>& nums, int target) {
5.         int left = 0;
6.         int right = nums.size();
8.         while(left < right) //left == right 没有意义
9.         {
10.             int mid = left+(right-left)/2;
11.             if(nums[mid] < target)
12.             {
13.                 left = mid+1;
14.             }
15.             else if(nums[mid] > target)
16.             {
17.                 right = mid;
18.             }
19.             else
20.             {
21.                 return mid;
22.             }
23.         }
24.         return -1;
25.     }
26. };

复制代码

2.2双指针法

什么是双指针法？

双指针法就是用两个指针来标记数组中的元素，可以大概提高遍历的服从。
我们平时遍历数组的时间，都是利用一个变量来标记数组遍历的位置，但是有些情况下，一个变量不够用，这个时间就可以考虑多利用一个变量；假如还是不够，你甚至还能再增加一个变量来标记。
例题

标题链接 —— 移除元素  (标题来源于力扣)
   标题：给你一个数组 nums 和一个值 val，你需要 原地 移除全部数值等于 val 的元素。元素的次序可能发生改变。然后返回 nums 中与 val 差别的元素的数量。
  标题分析

标题说要我们原地移除全部数值等于val元素，但是数组是连续的空间，假如在中间移除元素，就需要将背面全部的元素都向前移动一个位置，如许一来时间复杂的会非常大。所以，在办理数组中需要删除元素的时间，我们通常考虑找一个合适的值，利用覆盖来达到删除的目标。

解题代码

解法一：暴力解法

1. // 暴力解法
2. class Solution {
3. public:
4.     int removeElement(vector<int>& nums, int val) {
5.         int size = nums.size();
6.         for(int i = 0; i < size; ++i) // 遍历数组，找到需要删除的值
7.         {
8.             if(nums[i] == val) //就需要移除了
9.             {
10.                 // 从需要删除的值的后面找一个值来覆盖
11.                 for(int j = i+1; j < size; ++j)
12.                 {
13.                     nums[j-1] = nums[j];
14.                 }
15.                 i--;
16.                 size--;
17.             }
18.         }
20.         return size;
21.     }
22. };

复制代码

解法二：双指针法

1. // 双指针解法
2. class Solution {
3. public:
4.     int removeElement(vector<int>& nums, int val) {
5.         int fast = 0;
6.         int slow = 0;
7.         for(fast = 0; fast < nums.size(); ++fast)
8.         {
9.             if(nums[fast] != val)  // 找到不等于val的值放到前面去
10.             {
11.                 nums[slow++] = nums[fast];
12.             }
13.         }
15.         return slow;
16.     }
17. };

复制代码

双指针法对比与暴力解法，可以看出省略了一个查找替换循环的循环，镌汰了不须要的重复的查找。因此优化了代码的时间复杂度。

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。