数据结构与算法总结一（基于C/OC）


1.语言：C/OC

2.环境：Leetcode/Xcode



#1.数组

1.连续存储空间,对内存友好；

2.随机访问第K个元素，时间复杂度O(1)；

3.删除，插入操作时间复杂度取决于移动元素，O(n)；

小栗子：

#### [905. 按奇偶排序数组](https://leetcode-cn.com/problems/sort-array-by-parity/)

```
/**
 * Return an array of size *returnSize.
 * Note: The returned array must be malloced, assume caller calls free().
 */
#include <stdio.h>

int* sortArrayByParity(int* A, int ASize, int* returnSize) {
    *returnSize=ASize;
    int* temp=(int*)malloc(ASize*sizeof(int));
    for (int i = 0,j = 0,k = ASize-1;i < ASize;i++) {
        if (A[i] % 2 == 0) {
            temp[j] = A[i];
            j++;
        }
        else {
            temp[k] = A[i];
            k--;
        }
    }
    return temp;
}
```



#### [922. 按奇偶排序数组 II](https://leetcode-cn.com/problems/sort-array-by-parity-ii/)

```
/**
 * Return an array of size *returnSize.
 * Note: The returned array must be malloced, assume caller calls free().
 */
int* sortArrayByParityII(int* A, int ASize, int* returnSize) {
    *returnSize=ASize;
    int* temp=(int*)malloc(ASize*sizeof(int));
    for (int i = 0,j = 0,k = 1;i < ASize;i++) {
        if (A[i]%2 == 0) {
            temp[j] = A[i];
            j +=2;
        }
        else {
            temp[k] = A[i];
            k += 2;
        }
    }
    return temp;
}
```



# 2.链表

1.非连续存储空间，链式结构，对内存不友好;

2.访问第K个元素，时间复杂度O(n);

3.删除某个节点后的后继节点时间复杂度O(1)，在某个节点后插入节点时间复杂度O(1)；

4.双向链表,环形链表;



小栗子：

#### [83. 删除排序链表中的重复元素](https://leetcode-cn.com/problems/remove-duplicates-from-sorted-list/)

```
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode* deleteDuplicates(struct ListNode* head) {
    if (head == NULL ||head->next == NULL) {
        return head;
    }
    struct ListNode* p = head;
    int value = p->val;
    while(p->next != NULL) {
        if(p->next->val == value) {
            deleteNode(p);
        }
        //边界条件
        if (p->next != NULL) {
            if (p->next->val > value) {
            p = p->next;
            value = p->val;
          }
        }
    }
    return head;
}
//删除节点p的后继节点
void deleteNode(struct ListNode* p) {
    struct ListNode* q;
    if (p->next != NULL) {
        q = p->next;
        p->next = q->next;  
        q = NULL;
    }
}
```



#### [21. 合并两个有序链表](https://leetcode-cn.com/problems/merge-two-sorted-lists/)

```

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode* mergeTwoLists(struct ListNode* l1, struct ListNode* l2) {
    //向第一个比较小的链表插入,注意链表长度可能不等
    struct ListNode* w ,*head;
    if (l1 == NULL) {
        return l2;
    }
    if (l2 == NULL) {
        return l1;
    }
    if (l1->val < l2->val) {
        head = l1;
        l1 = l1->next;
    }
    else {
        head = l2;
        l2 = l2->next;
    }
    w = head;
    while(l1 != NULL && l2 != NULL) {
        if (l1->val < l2->val) {
            w->next = l1;
            l1 = l1->next;
        }
        else {
            w->next = l2;
            l2 = l2->next;
        }
        w = w->next;
    }
    if (l1 != NULL) {
        w->next = l1;
    }
    if (l2 != NULL) {
        w->next = l2;
    }
    return head;
}

```



# 3.栈与队列

1.栈：先进后出FILO，应用场景（1.iOS中页面导航，前进与后退；2.函数方法调用栈）

2.队列：先进先出，应用场景（1.线程队列）

小栗子：

[20. 有效的括号](https://leetcode-cn.com/problems/valid-parentheses/)

```
bool isValid(char* s) {
  int length = strlen(s);
  char* temp = (char*)malloc(length);
  int tail = 0;
  for (int i = 0;i < length;i++) {
    char value = s[i];
    if (value == '(' || value == '{' || value == '[' ) {
        temp[tail] = value;
        tail++;
    }
    else {
        if (tail == 0) {
            return false;
        }
        char now = temp[tail - 1];
        if ((now == '(' && value == ')') || (now == '{' && value == '}') || (now == '[' && value == ']')) {

        }
        else {
            return false;
        }
        tail--;
    }
  }
  if (tail != 0) {
    return false;
  }
  return true;
}
```



# 4.递归思想

1.如何写递归代码？

1.1 递归终止条件；

1.2 递推公式；

小栗子：见下面归并排序，快速排序。

# 5.排序

1.时间复杂度为O(n*n):

1.1冒泡排序（相邻元素交换，优化：1.当没有交换发生提前退出2.注意排序区间，减少遍历次数）；

```
/*
 注意值得比较 比较方式：相邻元素比较
 优化：1.比较次数 2.提前退出标志
 */
- (void)bubbleSort:(NSMutableArray*)array {
    if (array == nil) {
        return;
    }
    if (array.count <= 1) {
        return;
    }
    for (NSInteger i = 0;i < array.count;i++) {
        NSInteger flag = 0;
        for (NSInteger j = 0;j < array.count-1-i;j++) {
            if ([array[j] integerValue] > [array[j+1] integerValue]) {
                NSInteger temp = [array[j] integerValue];
                array[j] = array[j+1];
                array[j+1] = [NSNumber numberWithInteger:temp];
                flag = 1;
            }
        }
        if (!flag) {
            return;
        }
    }
}
```

1.2选择排序（基于比较，交换，每次遍历找到未排序区间最大/最小值）；

```
/*
 比较方式：每个位置依次找到最大最小值，依次比较
 优化：记录最小值位置，交换次数优化
 */
- (void)selectSort:(NSMutableArray*)array {
    if (array == nil) {
        return;
    }
    if (array.count <= 1) {
        return;
    }
    for (NSInteger i = 0;i < array.count;i++) {
        NSInteger minPos = i;
        for (NSInteger j = i+1; j < array.count;j++) {
            if ( [array[minPos] integerValue] > [array[j] integerValue]) {
                minPos = j;
            }
            if (j == array.count - 1) {
                NSInteger temp = [array[minPos] integerValue];
                array[minPos] = array[i];
                array[i] = [NSNumber numberWithInteger:temp];
            }
        }
        
    }
    
}
```

1.3选择排序（基于比较，移动元素）；

```
/*
 元素比较，元素移动
 已排序区间
 */
- (void)insertSort:(NSMutableArray*)array {
    if (array == nil) {
        return;
    }
    if (array.count <= 1) {
        return;
    }
    for (NSInteger i = 1;i < array.count;i++) {
        //要插入的数据
        NSInteger temp = [array[i] integerValue];
        NSInteger j = i-1;
        //已排序区间
        for (;j >= 0;--j) {
            //查找插入位置
            if ([array[j] integerValue] > temp) {
                //依次向后移动
                array[j+1] = array[j];
            }
            else {
                break;
            }
            
        }
        array[j+1] = [NSNumber numberWithInteger:temp];
    }
}
```

2.时间复杂度O(nlogn):

2.1归并排序（1.基于分治思想，递归思想主要关注点在merge函数，两个有序数组合并2.每次需要临时数组存储空间，不是原地排序算法3.稳定排序算法：顺序不变）；

```
//归并排序
- (void)mergeSort:(NSMutableArray*)array {
   NSMutableArray * res =  [self mergeSort:array begin:0 end:array.count-1];
    NSLog(@"res--%@",res);
}
- (NSMutableArray*)mergeSort:(NSMutableArray*)array begin:(NSInteger)begin end:(NSInteger)end {
    if (begin >= end) {
        return [NSMutableArray arrayWithObjects:array[begin], nil];
    }
    NSInteger middle = (begin+end)/2;
    NSMutableArray * leftArray = [self devidArray:array begin:begin end:middle];
    NSMutableArray * rightArray = [self devidArray:array begin:middle+1 end:end];
    [self mergeSort:leftArray begin:0 end:leftArray.count-1];
    [self mergeSort:rightArray begin:0 end:rightArray.count-1];
    NSMutableArray * res = [self mergeArray:leftArray right:rightArray ];
    return  res;
}
//分割数组
- (NSMutableArray*)devidArray:(NSMutableArray*)array begin:(NSInteger)begin end:(NSInteger)end {
    NSMutableArray * reslutArray = [NSMutableArray arrayWithCapacity:0];
    for (NSInteger i = begin;i <= end;i++) {
        [reslutArray addObject:array[i]];
    }
    return reslutArray;
}
//合并数组
- (NSMutableArray*)mergeArray:(NSMutableArray*)left right:(NSMutableArray*)right {
    NSMutableArray * resultArray = [NSMutableArray arrayWithCapacity:0];
    NSInteger i = 0;
    NSInteger j = 0;
    while (i < left.count && j < right.count) {
        NSInteger valueL = [left[i] integerValue];
        NSInteger valueR = [right[j] integerValue];
        if (valueL < valueR) {
            [resultArray addObject:[NSNumber numberWithInteger:valueL]];
            i++;
        }
        else {
            [resultArray addObject:[NSNumber numberWithInteger:valueR]];
            j++;
        }
    }
    if (i < left.count) {
        for (;i<left.count;i++) {
            [resultArray addObject:left[i]];
        }
    }
    if (j < right.count) {
        for (;j < right.count;j++) {
            [resultArray addObject:right[j]];
        }
    }
    return resultArray;
}

```

2.2快速排序（1.基于分治思想，递归思想关注点在分区函数，每次排序划分后的区间2.原地排序算法3.不稳定排序算法4.极端情况退化O(n*n),选择合适的分区函数）

```
//快速排序(这是分区函数拆分前)
- (void)quickSort:(NSMutableArray*)array begin:(NSInteger)begin end:(NSInteger)end {
    if (begin >= end) {
        return;
    }
   // NSInteger partition = [self partition:array left:begin right:end];
    
    NSInteger i = begin;
    NSInteger j = end;
    NSInteger key = end;
    while (i != j) {
        //注意前后顺序 下面顺序反了，所以错了, 如果key改为end，则能正确输出
        //key从头，先遍历尾;key从尾，先遍历头
        while (i<j && [array[i] integerValue] <= [array[key] integerValue]) {
            i++;
        }
        while (i<j && [array[j] integerValue] >= [array[key] integerValue]) {
            j--;
        }
        
        if (i < j) {
            [array exchangeObjectAtIndex:i withObjectAtIndex:j];
        }
        
    }
    [array exchangeObjectAtIndex:i withObjectAtIndex:end];
    
    [self quickSort:array begin:begin end:i - 1];
    [self quickSort:array begin:i + 1 end:end];
}
```

快速排序：

```
- (NSInteger)partition:(NSMutableArray*)array left:(NSInteger)left right:(NSInteger)right {
    NSInteger key = left;
    NSInteger i = left;
    NSInteger j = right;
    while (i != j) {
        while (i<j && [array[key] integerValue] <= [array[j] integerValue]) {
            j--;
        }
        while (i<j && [array[key] integerValue] >= [array[i] integerValue]) {
            i++;
        }
        if (i<j) {
            [array exchangeObjectAtIndex:i withObjectAtIndex:j];
        }
    }
    
    //最终将基准数归位, 因为i == j, 需要将<基数所在位置的value>与<i/j相等的位置的value>互换位置
    [array exchangeObjectAtIndex:i withObjectAtIndex:left];
    return i;
}
- (void)quickSort:(NSMutableArray*)array left:(NSInteger)left right:(NSInteger)right k:(NSInteger)k{
    if (left >= right) {
        return;
    }
    NSInteger partition = [self partition:array left:left right:right];
    //继续左边的排序
    [self quickSort:array left:left right:partition - 1 k:k];
    //继续右边的排序
    [self quickSort:array left:partition + 1 right:right k:k];
}
```

快排思想运用：O(n)时间复杂度求第K小（大）

```
//求第K小
- (NSInteger)findK:(NSMutableArray*)array begin:(NSInteger)begin end:(NSInteger)end indexOfK:(NSInteger)k {
    if (begin >= end) {
        return -1;
    }
    NSInteger partition = [self partition:array left:begin right:end];
    if (partition+1 == k) {
        return [array[partition] integerValue];
    }
    else if (k > partition+1) {
      return   [self findK:array begin:partition+1 end:end indexOfK:k];
    }
    else {
      return   [self findK:array begin:begin end:partition-1 indexOfK:k];
    }
    return -1;
    
}
```

3.线性排序/时间复杂度O(n)

3.1桶排序/计数排序 :针对数据范围不大的数据，将数据划分成不同的桶来实现排序;

3.2基数排序:要求数据可以划分成高低位，位之间有递进关系。

小栗子：

#### [242. 有效的字母异位词](https://leetcode-cn.com/problems/valid-anagram/)

```
给定两个字符串 s 和 t ，编写一个函数来判断 t 是否是 s 的一个字母异位词。

示例 1:

    输入: s = "anagram", t = "nagaram"
    输出: true

示例 2:

    输入: s = "rat", t = "car"
    输出: false

说明:

你可以假设字符串只包含小写字母。

进阶:

如果输入字符串包含 unicode 字符怎么办？你能否调整你的解法来应对这种情况？

bool isAnagram(char* s, char* t) {

    int sLength = strlen(s);
    int tLength = strlen(t);
    if (sLength != tLength) {
        return false;
    }
    int ts[26] = { 0 };
    int st[26] = { 0 };
    for (int i = 0;i < sLength;i++) {
        ts[s[i] - 'a'] ++;
        st[t[i] - 'a'] ++;
    }
    for (int i = 0;i < 26;i++) {
        if (ts[i] != st[i]) {
            return false;
        }
    }
    return true;

}
```



# 6.二分查找

1.适用场景有序集合，查找某一个元素时间复杂度O(logn)；

2.基于分治思想；

基础二分查找

```
- (NSInteger)binarySearch:(NSMutableArray*)array value:(NSInteger)value {
    NSInteger head = 0;
    NSInteger tail = array.count - 1;
    
    while (head <= tail) {
        NSInteger middle = head+(tail-head)/2;
        if ([array[middle] integerValue] > value) {
            tail = middle - 1;
        }
        else if ([array[middle] integerValue] < value) {
            head = middle + 1;
        }
        else {
            return middle;
        }
    }
    return -1;
}
```

查找一个小于等于给定值得元素

```
- (NSInteger)binarySearch:(NSMutableArray*)array lastSmallValue:(NSInteger)value {
    NSInteger head = 0;
    NSInteger tail = array.count - 1;
    while (head <= tail) {
        NSInteger middle = head + (tail-head)/2;
        if ([array[middle] integerValue] <= value) {
            if (middle == array.count - 1) {
                return middle;
            }
            else if (middle + 1 <=  array.count - 1) {
                if ([array[middle+1] integerValue] > value) {
                    return middle;
                }
                else {
                   head = middle + 1;
                }
            }
            else {
               head = middle + 1;
            }
            
        }
        else if ([array[middle] integerValue] > value) {
            
             tail = middle - 1;
        }
    }
    return -1;
}
```

第一个大于等于给定值

```
- (NSInteger)binarySearch:(NSMutableArray*)array firstBigValue:(NSInteger)value {
    NSInteger head = 0;
    NSInteger tail = array.count - 1;
    while (head <= tail) {
        NSInteger middle = head + (tail-head)/2;
        if ([array[middle] integerValue] >= value) {
            if (middle == 0) {
                return middle;
            }
            else if (middle - 1 >= 0) {
                if ([array[middle-1] integerValue] < value) {
                    return middle;
                }
                else {
                    tail = middle - 1;
                }
            }
            else {
                tail = middle - 1;
            }
            
        }
        else if ([array[middle] integerValue] <value) {
            head = middle + 1;
        }
    }
    return -1;
}
```

查找第一个值等于给定值

```
/*
 1.是不是第一个元素
 2.前一个元素是不是也等于value
 */
- (NSInteger)binarySearch:(NSMutableArray*)array firstValue:(NSInteger)value {
    NSInteger head = 0;
    NSInteger tail = array.count - 1;
    while (head <= tail) {
        NSInteger middle = head + (tail-head)/2;
        if ([array[middle] integerValue] > value) {
            tail = middle - 1;
        }
        else if ([array[middle] integerValue] <value) {
            head = middle + 1;
        }
        else {
            if (middle == 0) {
                return middle;
            }
            else if (middle >= 1) {
                if ([array[middle - 1] integerValue] != value) {
                    return middle;
                }
                else {
                    //向前找
                    tail = middle - 1;
                }
            }
            else {
                //向前找
                tail = middle - 1;
            }
        }
    }
    return -1;
}
```

最后一个值等于给定值

```
/*
 1.是不是最后一个元素
 2.后一个元素是不是也是value
 */
- (NSInteger)binarySearch:(NSMutableArray*)array lastValue:(NSInteger)value {
    NSInteger head = 0;
    NSInteger tail = array.count - 1;
    while (head <= tail) {
        NSInteger middle = head + (tail-head)/2;
        if ([array[middle] integerValue] > value) {
            tail = middle - 1;
        }
        else if ([array[middle] integerValue] <value) {
            head = middle + 1;
        }
        else {
            if (middle == array.count - 1) {
                return middle;
            }
            else if (middle+1 <= array.count - 1) {
                if ([array[middle + 1] integerValue] != value) {
                    return middle;
                }
                else {
                    //向后找
                    head = middle + 1;
                }
            }
            else {
                //向后找
                head = middle + 1;
            }
        }
    }
    return -1;
}
```

小栗子：

#### [441. 排列硬币](https://leetcode-cn.com/problems/arranging-coins/)

```
你总共有 *n *枚硬币，你需要将它们摆成一个阶梯形状，第 *k *行就必须正好有 *k *枚硬币。

给定一个数字 n，找出可形成完整阶梯行的总行数。

*n *是一个非负整数，并且在32位有符号整型的范围内。

示例 1:

    n = 5
    
    硬币可排列成以下几行:
    ¤
    ¤ ¤
    ¤ ¤
    
    因为第三行不完整，所以返回2.

int arrangeCoins(int n) {

    // int i = 0,sum = 0;
    // while(sum <= n) {
    //     i++;
    //     sum += i;
    // }
    // if (n - sum < i) {
    //    i--;
    // }
    return arrangeCoins2(n);

}

int arrangeCoins2(int n) {

    int low = 0, high = (1 << 16) - 1,mid = 0,sum = 0;
    while(low <= high) {
        mid = low + ((high-low)>>1);
        sum = ((mid&1) == 0) ? (mid/2) * (mid + 1) : ((mid + 1)/2) *mid;
        if (sum == n) {
            return mid;
        }
        else if(sum > n) {
            high = mid - 1;
        }
        else {
            low = mid + 1;
        }
    }
    return sum > n ? mid-1 : mid;

}



```





最后编辑于 ：
©著作权归作者所有,转载或内容合作请联系作者
  • 人面猴
    序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
    沈念sama阅读 206,839评论 6赞 482
  • 死咒
    序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
    沈念sama阅读 88,543评论 2赞 382
  • 救了他两次的神仙让他今天三更去死
    文/潘晓璐 我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
    开封第一讲书人阅读 153,116评论 0赞 344
  • 道士缉凶录：失踪的卖姜人
    文/不坏的土叔 我叫张陵，是天一观的道长。 经常有香客问我，道长，这世上最难降的妖魔是什么？ 我笑而不...
    开封第一讲书人阅读 55,371评论 1赞 279
  • 港岛之恋（遗憾婚礼）
    正文 为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
    茶点故事阅读 64,384评论 5赞 374
  • 恶毒庶女顶嫁案：这布局不是一般人想出来的
    文/花漫 我一把揭开白布。 她就那样静静地躺着，像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上，一...
    开封第一讲书人阅读 49,111评论 1赞 285
  • 城市分裂传说
    那天，我揣着相机与录音，去河边找鬼。 笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。 我是一名探鬼主播，决...
    沈念sama阅读 38,416评论 3赞 400
  • 双鸳鸯连环套：你想象不到人心有多黑
    文/苍兰香墨 我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
    开封第一讲书人阅读 37,053评论 0赞 259
  • 万荣杀人案实录
    序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
    沈念sama阅读 43,558评论 1赞 300
  • 护林员之死
    正文 独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 36,007评论 2赞 325
  • 白月光启示录
    正文 我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 38,117评论 1赞 334
  • 活死人
    序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
    沈念sama阅读 33,756评论 4赞 324
  • 日本核电站爆炸内幕
    正文 年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
    茶点故事阅读 39,324评论 3赞 307
  • 男人毒药：我在死后第九天来索命
    文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 30,315评论 0赞 19
  • 一桩弑父案，背后竟有这般阴谋
    文/苍兰香墨 我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 31,539评论 1赞 262
  • 情欲美人皮
    我被黑心中介骗来泰国打工， 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。 一个月前我还...
    沈念sama阅读 45,578评论 2赞 355
  • 代替公主和亲
    正文 我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
    茶点故事阅读 42,877评论 2赞 345