数据结构编程题 顺序表

删除最小值

题目描述

从顺序表中删除具有最小值的元素（假设唯一）并由函数返回被删元素的值。空出的位置由最后一个元素填补，若顺序表为空，则显示出错信息并退出运行。

解题代码

bool deleteMin(vector<int>& nums, int& val) {
    if (nums.empty()) {
        return false;
    }
    int minVal = INT32_MAX, minIdx = 0;
    for (int i = 0; i < nums.size(); ++i) {
        if (minVal > nums[i]) {
            minVal = nums[i];
            minIdx = i;
        }
    }
    nums[minIdx] = nums.back();
    val = minVal;
    return true;
}

逆置顺序表

题目描述

设计一个高效算法，将顺序表 L 的所有元素逆置，要求算法的空间复杂度为 O(1).

解题代码

void reverseList(vector<int>& nums) {
    int left = 0, right = nums.size() - 1;
    while (left < right) {
        swap(nums[left++], nums[right--]);
    }
}

删除特定值的元素

题目描述

对长度为 n 的顺序表 L，编写一个时间复杂度为 O(n)、空间复杂度为 O(1) 的算法，该算法删除线性表中的所有值为 x 的数据元素。

解题代码

void deleteX(vector<int>& nums, int x) {
    int n = nums.size(), xCnt = 0; // 记录当前遍历位置之前x的出现次数
    for (int i = 0; i < n; ++i) {
        nums[i - xCnt] = nums[i];
        xCnt += nums[i] == x;
    }
    nums.erase(nums.begin() + n - xCnt, nums.end()); // 删除冗余元素
}

删除特定区间内的元素

题目描述

从有序顺序表中删除其值在给定值 s 和 t 之间（要求 s < t）的所有元素，若 s 或 t 不合理或者顺序表为空，则显示错误信息并退出运行。

解题代码

bool deleteInterval(vector<int>& nums, int s, int t) {
    if (s >= t || nums.empty()) {
        return false;
    }
    int n = nums.size();
    int left = 0, right = n - 1;
    while (nums[left] < s) { // 找到首个不小于s的元素
        ++left;
    }
    while (nums[right] > t) { // 找到首个不大于t的元素
        --right;
    }
    int length = right - left + 1;
    for (int i = left; i + length < n; ++i) {
        nums[i] = nums[i + length]; // 移动元素
    }
    nums.erase(nums.begin() + n - length, nums.end());
    return true;
}

删除重复元素

题目描述

从有序顺序表中删除所有值重复的元素，使表中所有元素的值均不同。

解题代码

void deleteRedundancy(vector<int>& nums) {
    int reCnt = 0, n = nums.size();
    for (int i = 1; i < n; ++i) {
        if (nums[i] == nums[i - 1]) {
            ++reCnt;
        }
        else {
            nums[i - reCnt] = nums[i];
        }
    }
    nums.erase(nums.begin() + n - reCnt, nums.end());
}

合并有序顺序表

题目描述

将两个有序顺序表合并称为一个新的有序顺序表，并由函数返回结果顺序表。

解题代码

vector<int> mergeList(vector<int>& nums1, vector<int>& nums2) {
    int n1 = nums1.size(), n2 = nums2.size();
    vector<int> mergeNums(n1 + n2);
    int p1 = 0, p2 = 0, pm = 0;
    while (p1 < n1 && p2 < n2) {
        if (nums1[p1] < nums2[p2]) {
            mergeNums[pm++] = nums1[p1++];
        }
        else {
            mergeNums[pm++] = nums2[p2++];
        }
    }
    while (p1 < n1) {
        mergeNums[pm++] = nums1[p1++];
    }
    while (p2 < n2) {
        mergeNums[pm++] = nums2[p2++];
    }
    return mergeNums;
}

替换线性表位置

题目描述

已知在一维数组 A[m + n] 中依次存放两个线性表（a1, a2, …, am）和（b1, b2, …, bn）。编写一个函数，将数组中两个顺序表的位置互换，即将（b1, b2, …, bn）放在（a1, a2, …, am）的前面。

解题代码

void swapList(vector<int>& nums, int m, int n) {
    for (int i = 0, j = m + n - 1; i < j; ++i, --j) {
        swap(nums[i], nums[j]); // 整体逆置
    }
    for (int i = 0, j = n - 1; i < j; ++i, --j) {
        swap(nums[i], nums[j]); // 前n个元素逆置
    }
    for (int i = n, j = m + n - 1; i < j; ++i, --j) {
        swap(nums[i], nums[j]); // 后m个元素逆置
    }
}

查找有序表中的特定值元素

题目描述

线性表（a1, a2, …, an）中的元素递增有序且按顺序存储在计算机内。要求设计一个算法，完成用最少时间在表中查找值为 x 的元素，若找到，则将其与后继元素位置相交换。若找不到，则将其插入表中并使表中元素仍然递增有序。

解题代码

void searchX(vector<int>& nums, int x) {
    int left = 0, right = nums.size() - 1;
    while (left <= right) {
        int mid = (left + right) / 2; // 二分查找
        if (x == nums[mid]) {
            if (mid != nums.size() - 1) {
                swap(nums[mid], nums[mid + 1]);
            }
            return;
        }
        else if (x < nums[mid]) {
            right = mid - 1;
        }
        else {
            left = mid + 1;
        }
    }
    nums.insert(nums.begin() + left, x); // 查找失败，插入x
}

查找两个序列的中位数

题目描述

一个长度为 L（L >= 1） 的升序序列 S，处在第 ⌈L / 2⌉ 个位置的数称为 S 的中位数。例如，若序列 S1 = (11, 13, 15, 17, 19)，则 S1 的中位数是 15，两个序列的中位数是含它们所有元素的升序序列的中位数。例如，若 S2 = (2, 4, 6, 8, 20)，则 S1 和 S2 的中位数为 11。现在有两个等长升序序列 A 和 B，试设计一个在时间和空间两方面都尽可能高效的算法，找出两个序列 A 和 B 的中位数。

解题代码

int searchMedian(vector<int>& nums1, vector<int>& nums2) {
    int n = nums1.size();
    int left1 = 0, right1 = n - 1, left2 = 0, right2 = n - 1;
    while (left1 < right1 && left2 < right2) {
        int mid1 = (left1 + right1) / 2;
        int mid2 = (left2 + right2) / 2;
        if (nums1[mid1] == nums2[mid2]) {
            return nums1[mid1];
        }
        else if (nums1[mid1] < nums2[mid2]) {
            // 判断区间长度的奇偶性以确保 nums1 和 nums2 区间长度相等
            if ((right1 - left1) % 2 == 0) {
                left1 = mid1;
                right2 = mid2;
            }
            else {
                left1 = mid1 + 1;
                right2 = mid2;
            }
        }
        else {
            if ((right2 - left2) % 2 == 0) {
                right1 = mid1;
                left2 = mid2;
            }
            else {
                right1 = mid1;
                left2 = mid2 + 1;
            }
        }
    }
    return min(nums1[left1], nums2[left2]);
}

数组的主元素

题目描述

已知一个整数序列 A = (a0, a1, …, an - 1)，其中 0 <= ai < n（0 <= i < n）。若存在 ap1 = ap2 = … = apm = x 且 m > n / 2（0 <= pk < n, 1 <= k <= m），则称 x 为 A 的主元素。例如 A = (0, 5, 5, 3, 5, 7, 5, 5)，则 5 为主元素；又如 A = (0, 5, 5, 3, 5, 1, 5, 7)。则 A 中没有主元素。假设 A 中的 n 个元素保存在一个一维数组中，请设计一个尽可能高效的算法，找出 A 的主元素。若存在主元素，则输出该元素；否则输出 -1。

解题代码

int getMainElem(vector<int>& nums) {
    int n = nums.size();
    int mainElem = -1, cnt = 0; 
    for (int i = 0; i < n; ++i) { // 找出可能为主元素的元素
        if (nums[i] == mainElem) {
            ++cnt;
        }
        else if (cnt > 0) {
            --cnt;
        }
        else {
            mainElem = nums[i];
            cnt = 1;
        }
    }
    cnt = 0;
    for (int i = 0; i < n; ++i) { // 判断该元素是否为主元素
        cnt += nums[i] == mainElem;
    }
    return cnt > n / 2 ? mainElem : -1;
}

未出现的最小正整数

题目描述

给定一个含 n（n >= 1）个整数的数组，请设计一个在时间上和空间上尽可能高效的算法，找出数组中未出现的最小正整数。例如，数组 {-5, 3, 2, 3} 中未出现的最小正整数为 1；数组 {1, 2, 3} 中未出现的最小正整数为 4。

解题代码

int getMinPositive(vector<int>& nums) {
    int n = nums.size();
    vector<bool> numSet(n, false);
    for (int i = 0; i < n; ++i) {
        if (nums[i] > 0 && nums[i] <= n) {
            numSet[nums[i] - 1] = true;
        }
    }
    for (int i = 0; i < n; ++i) {
        if (!numSet[i]) {
            return i + 1;
        }
    }
    return n + 1;
}