学校网站的功能,网站多久才能在百度上收到,凉山建设局网站,手机客户端app下载安装数组篇 26.删除有序数组中的重复项题目详情题解 27. 移除元素题解 35. 搜索插入位置题目详情题解 66. 加1题目详情题解 88. 合并两个有序数组题目详情题解 108. 将有序数组转换为二叉搜索树题目详情题解注意 118. 杨辉三角题目详情题解 119. 杨辉三角 II题目详情题解 136. 只出… 数组篇 26.删除有序数组中的重复项题目详情题解 27. 移除元素题解 35. 搜索插入位置题目详情题解 66. 加1题目详情题解 88. 合并两个有序数组题目详情题解 108. 将有序数组转换为二叉搜索树题目详情题解注意 118. 杨辉三角题目详情题解 119. 杨辉三角 II题目详情题解 136. 只出现一次的数字题目详情题解 169. 多数元素题目详情题解摩尔投票算法摩尔投票算法的优点摩尔投票算法的缺点 26.删除有序数组中的重复项
题目详情
给你一个 非严格递增排列 的数组 nums 请你 原地 删除重复出现的元素使每个元素 只出现一次 返回删除后数组的新长度。元素的 相对顺序 应该保持 一致 。然后返回 nums 中唯一元素的个数。
考虑 nums 的唯一元素的数量为 k 你需要做以下事情确保你的题解可以被通过
更改数组 nums 使 nums 的前 k 个元素包含唯一元素并按照它们最初在 nums 中出现的顺序排列。nums 的其余元素与 nums 的大小不重要。 返回 k 。
题解
int removeDuplicates(int* nums, int numsSize) {int i0,count;for(int j1;jnumsSize;j){if(nums[i]!nums[j])nums[i]nums[j];}counti1; // i是数组下标,count应该比i多1.return count;
}27. 移除元素
##题目详情 给你一个数组 nums 和一个值 val你需要 原地 移除所有数值等于 val 的元素并返回移除后数组的新长度。
不要使用额外的数组空间你必须仅使用 O(1) 额外空间并 原地 修改输入数组。
元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。
题解
int removeElement(int* nums, int numsSize, int val) {int count0; // 记录val值的个数for(int i0;inumsSize;i){if(nums[i]val) // 数组的值等于val值,countcount;elsenums[i-count]nums[i];}return numsSize-count;
}35. 搜索插入位置
题目详情
给定一个排序数组和一个目标值在数组中找到目标值并返回其索引。如果目标值不存在于数组中返回它将会被按顺序插入的位置。
请必须使用时间复杂度为 O(log n) 的算法。
题解
int searchInsert(int* nums, int numsSize, int target) {int low0,highnumsSize-1;while(lowhigh){int mid(lowhigh)/2;if(nums[mid]target)return mid;else if(nums[mid]target)highmid-1;elselowmid1;}return low; // low指向的位置是target元素应该在数组中存放的位置
}66. 加1
题目详情
给定一个由 整数 组成的 非空 数组所表示的非负整数在该数的基础上加一。
最高位数字存放在数组的首位 数组中每个元素只存储单个数字。
你可以假设除了整数 0 之外这个整数不会以零开头。
题解
int* plusOne(int* digits, int digitsSize, int* returnSize) {for(int idigitsSize-1;i0;i--){if(digits[i]9){digits[i];(*returnSize)digitsSize;return digits;}else{digits[i]0;}}int* res(int*)malloc(sizeof(int)*(digitsSize1));res[0]1;for(int i1;idigitsSize1;i)res[i]digits[i-1];(*returnSize)digitsSize1;return res;
}88. 合并两个有序数组
题目详情
给你两个按 非递减顺序 排列的整数数组 nums1 和 nums2另有两个整数 m 和 n 分别表示 nums1 和 nums2 中的元素数目。
请你 合并 nums2 到 nums1 中使合并后的数组同样按 非递减顺序 排列。
注意最终合并后数组不应由函数返回而是存储在数组 nums1 中。为了应对这种情况nums1 的初始长度为 m n其中前 m 个元素表示应合并的元素后 n 个元素为 0 应忽略。nums2 的长度为 n 。
题解
void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n) {int i, j 0, k 0, tempNums1[nums1Size];for (i 0; i m; i) // 移动元素到tempNums1中tempNums1[i] nums1[i];i 0;while (i m j n) {if (tempNums1[i] nums2[j]) {nums1[k]tempNums1[i];}else{nums1[k]nums2[j];}}while(im){nums1[k]tempNums1[i];}while(jn){nums1[k]nums2[j];}
}108. 将有序数组转换为二叉搜索树
题目详情
给你一个整数数组 nums 其中元素已经按 升序 排列请你将其转换为一棵 高度平衡 二叉搜索树。
高度平衡 二叉树是一棵满足「每个节点的左右两个子树的高度差的绝对值不超过 1 」的二叉树。
题解
/*** Definition for a binary tree node.* struct TreeNode {* int val;* struct TreeNode *left;* struct TreeNode *right;* };*/
struct TreeNode* travel(int nums[],int low,int high){if(lowhigh) return NULL;int mid(lowhigh)/2;struct TreeNode* root(struct TreeNode*)malloc(sizeof(struct TreeNode));root-valnums[mid];root-lefttravel(nums,low,mid-1);root-righttravel(nums,mid1,high);return root;
}struct TreeNode* sortedArrayToBST(int* nums, int numsSize) {struct TreeNode* headtravel(nums,0,numsSize-1);return head;
}注意
// 第一种
struct TreeNode{int data;struct TreeNode* left;struct TreeNode* right;
}TLnode;// 第二种
struct TreeNode{int data;struct TreeNode* left;struct TreeNode* right;
};// 为第一种的话函数的返回值可以写为 TLnode 或 struct TreeNode
// 为第一种的话函数的返回值可以写为 struct TreeNode118. 杨辉三角
题目详情
给定一个非负整数 numRows生成「杨辉三角」的前 numRows 行。
在「杨辉三角」中每个数是它左上方和右上方的数的和。
题解
int** generate(int numRows, int* returnSize, int** returnColumnSizes){//返回的是二维数组所以需要保存每一行的信息*returnSize numRows; // 返回有几列*returnColumnSizes (int *)malloc(sizeof(int)*numRows);//returnColumnSizes储存杨辉三角每一行元素的个数int** res (int**)malloc(sizeof(int*)*numRows);for (int i 0; i numRows; i) {(*returnColumnSizes)[i] i1;res[i] (int*)malloc(sizeof(int)*(i1));res[i][0] 1;res[i][i] 1;for (int j 1; j i; j) {res[i][j] res[i-1][j] res[i-1][j-1]; }}return res;
}119. 杨辉三角 II
题目详情
给定一个非负索引 rowIndex返回「杨辉三角」的第 rowIndex 行。
在「杨辉三角」中每个数是它左上方和右上方的数的和。 示例 1:
输入: rowIndex 3 输出: [1,3,3,1] 示例 2:
输入: rowIndex 0 输出: [1] 示例 3:
输入: rowIndex 1 输出: [1,1]
题解
int* getRow(int rowIndex, int* returnSize) {*returnSize (rowIndex 1);int** arr (int**)malloc(sizeof(int*) * (rowIndex1));int i, j;for (i 0; i rowIndex1; i) {arr[i] (int*)malloc(sizeof(int) * (i 1));arr[i][0] 1;arr[i][i] 1;for (j 1; j i; j) {arr[i][j] arr[i - 1][j - 1] arr[i - 1][j];}}return arr[rowIndex];
}136. 只出现一次的数字
题目详情
给你一个 非空 整数数组 nums 除了某个元素只出现一次以外其余每个元素均出现两次。找出那个只出现了一次的元素。
你必须设计并实现线性时间复杂度的算法来解决此问题且该算法只使用常量额外空间。
示例 1
输入nums [2,2,1] 输出1 示例 2
输入nums [4,1,2,1,2] 输出4 示例 3
输入nums [1] 输出1
题解
int singleNumber(int* nums, int numsSize) {int res0;for(int i0;inumsSize;i)res^nums[i];return res;
}169. 多数元素
题目详情
给定一个大小为 n 的数组 nums 返回其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。
你可以假设数组是非空的并且给定的数组总是存在多数元素。
示例 1
输入nums [3,2,3] 输出3 示例 2
输入nums [2,2,1,1,1,2,2] 输出2
题解
int majorityElement(int* nums, int numsSize) {int i, vote 0,elector; // vote 投票数 elector 选举者(把数组里面的数字看做选举者)for (i 0; i numsSize; i) {if (!vote) {elector nums[i];}if (elector nums[i])vote;elsevote--;}return elector;
}摩尔投票算法
该算法的核心就是对拼消耗
摩尔投票算法的优点
时间复杂度低算法只需要遍历数组两次时间复杂度为O(n)其中n是数组长度。 空间复杂度低算法只需要常数级的额外空间因此空间复杂度为O(1)。 ● 高效适用于大规模数据能够在较短时间内找到主要元素。
摩尔投票算法的缺点
不适用于所有情况算法要求主要元素的出现次数超过一半因此对于没有主要元素的情况不适用。 需要额外验证算法找到候选主要元素后还需要额外的遍历来验证其是否真的满足条件。 摩尔投票算法
