【LeetCode题集】 线性枚举的原地算法入门，这一篇就够了

目录

2057. 值相等的最小索引

26. 删除有序数组中的重复项 

 217. 存在重复元素

 2154. 将找到的值乘以 2

27. 移除元素 

这是一篇LeetCode入门级级题目解析，适合刚开始学习C语言或者刚开始刷力扣题目的同学。

题目都相对简单，相信大家都能够看得懂。如果对你有所帮助，我万分荣幸！

2057. 值相等的最小索引

题目：给你一个下标从 0 开始的整数数组 nums ，返回 nums 中满足 i mod 10 == nums[i] 的最小下标 i ；如果不存在这样的下标，返回 -1 。

x mod y 表示 x 除以 y 的 余数 。

题目传送门

解题思路：

线线扫描：若找到符合条件的下标就返回，若遍历完还没找到，就返回-1. 

int smallestEqual(int* nums, int numsSize) {    for(int i=0; i<numsSize; i++)    { if(nums[i] == i%10) {     return i; }    }    return -1;} 

26. 删除有序数组中的重复项 

题目：给你一个 升序排列 的数组 nums ，请你 原地 删除重复出现的元素，使每个元素 只出现一次 ，返回删除后数组的新长度。元素的 相对顺序 应该保持 一致 。
由于在某些语言中不能改变数组的长度，所以必须将结果放在数组nums的第一部分。更规范地说，如果在删除重复项之后有 k 个元素，那么?nums?的前 k 个元素应该保存最终结果。
将最终结果插入?nums 的前 k 个位置后返回 k 。
不要使用额外的空间，你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成。

题目传送门

解题思路：

法一：利用两个指针，快的用来扫描数组，慢的用来记录不重复数组的最大下标。
fast扫描数组，如果找到相邻的数组值不一样，就把fast指向的的数组值赋给low指向的位置，low值加一，fast继续扫描，直到扫描完数组所有的值为止。

 fast扫描完后，low指向的位置是不重复数组最大下标的下一个位置，可表示不重复数组的大小，故，直接返回low即可。

int removeDuplicates(int* nums, int numsSize){    if(numsSize == 0)    { return 0;    }    int low=1;    int fast=1;    while(fast<numsSize)    { if(nums[fast]!=nums[fast-1]) {     nums[low]=nums[fast];     low++; } fast++;    }    return low;}

 法二：利用两个指针，快的用来扫描数组，慢的用来记录当前不重复数组的最大下标。
fast扫描数组，若遇到fast指向的数组值不等于low指向的值时，先让low加一，再把fast指向的值赋给low，直到fast扫描完数组为止。
扫描结束，low指向的是不重复数组的最大下标，不是不重复数组的大小，故要返回low+1表示数组大小。

int removeDuplicates(int* nums, int numsSize){    int low = 0;    int fast = 0;    while(fast < numsSize)    { if(nums[fast] != nums[low]) {     low++;     nums[low] = nums[fast]; } fast++;    }    return low+1;}

 217. 存在重复元素

题目：给你一个整数数组 nums 。如果任一值在数组中出现 至少两次 ，返回 true ；如果数组中每个元素互不相同，返回 false 。

题目传送门

解题思路：

法一：枚举法。两次遍历查找重复元素，时间复杂度为O(n^2),超出时间限制 

bool containsDuplicate(int* nums, int numsSize){    if(numsSize <= 1)    {    return false;}    for(int i=0; i<numsSize-1; i++)    { for(int j=i+1; j<numsSize; j++) {     if(nums[i] == nums[j])     {     return true;} }    }    return false;}

 法二：排序 ,若相邻元素值相等，则说明有重复元素，时间复杂度为:O(nlogn) 

int cmp(const void* _a, const void* _b) {    int* a = (int*)_a；int* b = (int*)_b;//return *a > *b;     return *a - *b;   //升序排序 }bool containsDuplicate(int* nums, int numsSize) {    qsort(nums, numsSize, sizeof(int), cmp);    for (int i=0; i<numsSize-1; i++) { if (nums[i] == nums[i+1]) {     return true; }    }    return false;}

法三：哈希表

对于数组中每个元素，我们将它插入到哈希表中。如果插入一个元素时发现该元素已经存在于哈希表中，则说明存在重复的元素。

C语言哈希表参考学习

struct hashTable {    //定义哈希表    int key;    UT_hash_handle hh;};bool containsDuplicate(int* nums, int numsSize) {    struct hashTable* set = NULL;    for (int i = 0; i key = nums[i];     HASH_ADD_INT(set, key, tmp); } else {     return true; }    }    return false;}

 2154. 将找到的值乘以 2

题目：给你一个整数数组 nums ，另给你一个整数 original ，这是需要在 nums 中搜索的第一个数字。
接下来，你需要按下述步骤操作：
如果在 nums 中找到 original ，将 original乘以 2 ，得到新 original（即，令 original = 2 * original）。
否则，停止这一过程。
只要能在数组中找到新 original ，就对新 original 继续 重复 这一过程。
返回 original 的 最终 值。 

题目传送门

解题思路：

方法：排序，依次找数组中是否有等于original的值，如果有，就把original*2.由于大的数字都排在后面，故不会漏值 

int cmp(const void* _a, const void* _b){    int* a = (int*)_a;    int* b = (int*)_b;    return *a > *b;}int findFinalValue(int* nums, int numsSize, int original){   /*陷阱：original*2以后，在已经遍历过的部分可能会找到新的original，由于遍历不会返回就会导致漏值     for(int i=0; i<numsSize; i++)    { if(nums[i] == original) {     original = 2*original; }    }    return original;    */    qsort(nums, numsSize, sizeof(int), cmp);    for(int i=0; i<numsSize; i++)    { if(original == nums[i]) {     original = 2*original; }      }     return original;}

 提供一种思路：若在数组中找到等于original的元素就从新遍历数组，一直循环的遍历数组，直到数组中没有等于original的元素。该方法时间复杂度过高，故不推荐，可以作为扩展思路。 

27. 移除元素 

题目：给你一个数组 nums和一个值 val，你需要 原地 移除所有数值等于?val?的元素，并返回移除后数组的新长度。
不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并 原地 修改输入数组。
元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。

题目传送门

解题思路：

法一：快慢指针 
用两个指针，快的用来扫描数组，慢的用来记录不含val值的数组的最大下标。
fast扫描数组，如果fast指向的元素值不等于val，就把fast指向的的数组值赋给low指向的位置，low值加一，fast继续扫描，直到扫描完数组所有的值为止
 fast扫描完后，low指向的位置是不重复数组最大下标的下一个位置，可表示不重复数组的大小，故，直接返回low即可。 

int removeElement(int* nums, int numsSize, int val){    if(numsSize == 0)    { return 0;    }    int low = 0;    int fast = 0;    while(fast != numsSize)    { if(nums[fast] != val) {     nums[low] = nums[fast];     low++; } fast++;    }    return low;}

法二：双指针 (次方法非本人想到的，参考了leetcode官方题解，但学会了就成了我们自己的东西)此法改变原数组元素间的相对位置 
使用双指针，两个指针初始时分别位于数组的首尾，向中间移动遍历该序列。
如果左指针left 指向的元素等于val，此时将右指针right 指向的元素复制到左指针
left的位置，然后右指针right左移一位。如果赋值过来的元素恰好也等于val，可以
 继续把右指针right 指向的元素的值赋值过来（左指针left 指向的等于val 的元素的位
 置继续被覆盖），直到左指针指向的元素的值不等于val 为止。
当左指针eft 和右指针 right 重合的时候，左右指针遍历完数组中所有的元素。
这样的方法两个指针在最坏的情况下合起来只遍历了数组一次。

与方法一不同的是，方法二避免了需要保留的元素的重复赋值操作。

int removeElement(int* nums, int numsSize, int val){    int left = 0;    int right = numsSize;    while(left < right)    { if(nums[left] == val) {     nums[left] = nums[right-1];     right--; } else {     left++; }    }    return left;}