数据结构（一）：数组及面试常考的算法_数据结构常考算法

数据结构是计算机存储、组织数据的方式。一种好的数据结构可以带来更高的运行或者存储效率。数据在内存中是呈线性排列的，但是我们可以使用指针等道具，构造出类似“树形”的复杂结构。下面介绍八个常见的数据结构。

数据结构分为线性数据结构和非线性数据结构。

线性数据结构包括：数组（Array）、链表（Linked List）、栈（Stack）、队（Queue）。

非线性数据结构包括：树（Tree）、堆（Heap）、散列表（Hashing）、图（Graph）。

一、数组介绍

1、定义

数组是一种线性结构，而且在物理内存中也占据着一块连续空间。数组分为一维数组和多维数组两种类型。

2、优缺点及使用场景

优点：访问数据简单。

缺点：添加和删除数据比较耗时间。

使用场景：频繁查询，对存储空间要求不大，很少增加和删除的情况。

3、增删改查

数据访问：由于数据是存储在连续空间内，所以每个数据的内存地址都是通过数据小标算出，所以可以直接访问目标数据。（这叫做“随机访问”）。

数据添加：数据添加需要移动其他数据。首先增加足够的空间，然后把已有的数据一个个移开。

数据删除：如果想要删除数据，也是一样挨个把数据往反方向移动。

4、数组的基本操作

Insert--在指定索引位置插入一个元素。

Get--返回指定索引位置的元素。

Delete--删除指定索引未知的元素。

Size--得到数组所有元素的数量。

二、常考算法

1. 寻找数组中第二小(大)的元素。

思路：

(1)先定义一个min和second_min,将数组中第一个元素赋值给min，第二个元素赋值个second_min。

(2)判断数组第一个和第二个元素的大小，交换最小值和第二小值。

(3)从数组第3个元素开始遍历,分别与当前最小值min和第二小值second_min比较, 如果当前数组元素小于当前最小值min, 那么当前最小值就是第二最小值;如果当前元素小于第二最小值second_min,那么当前元素就是第二最小值。

// 时间复杂度为O(n)
int SearchSecondMin(int nums[], int length){
    int min = nums[0];  //假设数组中第一个元素是最小值
    int second_min = nums[1]; //数组中第二个元素是第二小值
    if(length < 2 || nums == NULL){
        return -1;
    }
    // 判断数组第一个和第二个元素的大小，交换最小值和第二小值
    if( min > second_min){
        min = nums[1];
        second_min = nums[0];
    }
    // 从数组第3个元素开始遍历,分别与当前最小值和第二小值比较,
    // 如果当前元素小于当前最小值, 那么当前最小值就是第二最小值;如果当前元素小于第二最小值,那么当前元素就是第二最小值.
    for(int i = 2; i < length; i++){
        if(nums[i] < min){
            second_min = min;
            min = nums[i];  
        }
        else if (nums[i] < second_min)
        {
            second_min = nums[i];
        }
    }
    cout<<"数组中第二小的元素为："<< second_min <<endl; 
    return second_min; 
}
 
// 类似的,寻找数组中第二大的元素
int SearchSecondBig(int nums[], int length){
    int max = nums[0];
    int second_max = nums[1];
    if(nums == NULL || length < 2){
        return -1;
    }
    if(max < second_max){
        max = nums[1];
        second_max = nums[0];
    }
    for (int i = 2; i < length; i++){
        if(nums[i] > max){
            second_max = max;
            max = nums[i];
        }
        else if (nums[i] > second_max)
        {
            second_max = nums[i];
        }
    }
    cout<<"数组中第二大的元素为："<< second_max <<endl;
    return second_max;    
}
 
 
int main(){
    int nums[] = {-2,0,4,3,-1};
    int length = sizeof(nums) / sizeof(nums[0]);
    SearchSecondMin(nums, length);
    SearchSecondBig(nums, length);
    return 0;
}

2、找到数组中第一个不重复的出现的整数。

思路：使用两个循环。外部循环逐个遍历元素，内部循环检查元素是否存在多次或不存在。

#include<iostream>
using namespace std;
 
// 两层for循环
int SearchFirstUnrepeat(int nums[], int length){
    int unrepeat;
    // 外层循环逐个遍历元素
    for(int i = 0; i < length; i++){
        int j;
        // 内层循环判断元素是否存在多次或不存在
        for(j = 0; j < length; j++){
            if(i != j && nums[i] == nums[j]){
                break;
            }
        }
        if(j == length){ //如果j遍历到最后没有找到重复的元素，就返回当前i对应的元素
            unrepeat = nums[i];
            return unrepeat; //return跳出循环
        }
    }
    return -1;
}
 
int main(){
 int nums[] = {1,2,1,3,4};
 int length = sizeof(nums) / sizeof(nums[0]);
 int result = SearchFirstUnrepeat(nums, length);
 cout << "数组中第一个不重复的元素是" << result << endl;
}

2. 合并两个有序数组。

题目：已知两个有序数组，合并两个有序数组，并且要求重复元素只出现一次。如nums1={2,3,3,5,7,8}，nums2={3,3,5,8}。合并后数组：nums={2,3,5,7,8}。

思路：

第一步：利用双指针法（快慢指针）去掉两个有序数组中的重复元素（只出现一次）。

第二步：利用双指针法分别指向两个数组，比较两个有序数组的元素。若nums1<nums2,指向nums1的指针+1，若nums2<nums1，指向nums2的指针+1，若nums1==nums2，同时＋1。

#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
 
//双指针法：去掉数组中重复项
vector<int> removeDuplicates(int nums[], int length){
    int fastIndex, slowIndex=0;
    vector<int> vint;
    for(fastIndex = slowIndex + 1; fastIndex < length; fastIndex++){
        //找到了不与nums[slowIndex]的重复的值,则将不重复的值赋值放在slowIndex的后面一位，同时slowIndex的下标后移一位，开始下一个数的重复判断。
        if(nums[fastIndex] != nums[slowIndex]){
            nums[++slowIndex] = nums[fastIndex];
        }
    }
    for(int i = 0; i < slowIndex + 1; i++){
        vint.push_back(nums[i]);
    }
    return vint;
}
// 合并两个有序数组
void addTwoNums(int a[], int b[], int a_length, int b_length){
    // 去掉nums1和nums2里的重复元素（重复元素只算一次）
    vector<int> vInt1, vInt2;
    vInt1 = removeDuplicates(a, a_length);
    vInt2 = removeDuplicates(b, b_length);
    cout << "nums1去重后的数组：" ;
    for(int i = 0; i < vInt1.size(); i++){
        cout << vInt1[i] << " ";
    }
    cout << endl;
    cout << "nums2去重后的数组：" ;
    for(int i = 0; i < vInt2.size(); i++){
        cout << vInt2[i] << " ";
    }
    cout<<endl<<"合并nums1与nums2：";
    
    // 合并两个有序数组
    vector<int> nums;
    int i = 0, j=0;
    while((i != vInt1.size()) && (j != vInt2.size())){
        if(vInt1[i] == vInt2[j]){
            nums.push_back(vInt1[i]);
            i++;
            j++;
        }
        else if(vInt1[i] < vInt2[j]){
            nums.push_back(vInt1[i]);
            i++;
        }
        else{
            nums.push_back(vInt2[j]);
            j++;
        }
    }
    for(auto c: nums){
        cout << c << " ";
    }
}
 
int main(){
    int nums1[] = {2,3,3,5,7,8};
    int nums2[] = {3,3,5,8};
    int nums1_length = sizeof(nums1) / sizeof(nums1[0]);
    int nums2_length = sizeof(nums2) / sizeof(nums2[0]);
    addTwoNums(nums1,nums2, nums1_length, nums2_length);
}

4、重新排列数组中的正数和负数。

题目：对数组中的正负数重新排序，使负数排在正数之前。如nums={8, 4, 5, -2, 6, -3, 5}，输出nums={-3 -2 5 4 6 8 5}。

思路：采用双指针，使从前往后第i个负数和从后往前第j个正数交换位置。

#include<iostream>
using namespace std;
 
// 对数组中的正负数重新排序，使负数排在正数之前
void RealignmentNumbers(int nums[], int length){
    int i = 0, j = length - 1;
    // 采用双指针，规定i指向的数是正数，j指向的数是负数。
    while(i != j){
        while(nums[i] < 0)
            i++;
        while(nums[j] > 0)
            j--;
        if(i == length - 1 || j == 0)
            break;
        int temp;
        temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
        i++;
        j--;
    }
    for(int m = 0; m < length; m++){
        cout << nums[m] << " ";
    }
}
 
int main(){
 int nums[] = {8, 4, 5, -2, 6, -3, 5};
 int length = sizeof(nums) / sizeof(nums[0]);
 RealignmentNumbers(nums, length);
 return 0;
}