数组(Array)和排序
source link: https://senitco.github.io/2018/03/25/data-structure-array-sort/
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
数组(Array)和排序
数据结构与算法中数组（Array）问题总结归纳。
Merge Intervals
Given a collection of intervals, merge all overlapping intervals. For example, Given [1,3],[2,6],[8,10],[15,18], return [1,6],[8,10],[15,18].
* Definition for an interval. * struct Interval { * int start; * int end; * Interval() : start(0), end(0) {} * Interval(int s, int e) : start(s), end(e) {}//先按元组第一个元素排序，然后判断相邻元组是否存在重叠区间vector<Interval> merge(vector<Interval>& intervals) vector<Interval> result; int size = intervals.size(); sort(intervals.begin(), intervals.end(), [](const Interval& r1, const Interval& r2) {return r1.start < r2.start; }); for(int i = 0; i < size;) int j = i + 1; for(; j < size && intervals[i].end >= intervals[j].start; j++) if(intervals[j].end > intervals[i].end) intervals[i].end = intervals[j].end; result.push_back(intervals[i]); return result;vector<Interval> merge(vector<Interval>& intervals) if(intervals.size() <= 1) return intervals; vector<Interval> result; sort(intervals.begin(), intervals.end(), [](const Interval& r1, const Interval& r2) {return r1.start < r2.start; }); Interval tmp(intervals[0]); for(int i = 1; i < intervals.size(); i++) if(tmp.end >= intervals[i].start) tmp.end = max(tmp.end, intervals[i].end); result.push_back(tmp); tmp = intervals[i]; result.push_back(tmp); //添加最后一个元组 return result;Insert Interval
Given a set of non-overlapping intervals, insert a new interval into the intervals (merge if necessary). You may assume that the intervals were initially sorted according to their start times.
Example 1: Given intervals [1,3],[6,9], insert and merge [2,5] in as [1,5],[6,9].
Example 2: Given [1,2],[3,5],[6,7],[8,10],[12,16], insert and merge [4,9] in as [1,2],[3,10],[12,16]. This is because the new interval [4,9] overlaps with [3,5],[6,7],[8,10].
先拷贝newInterval前的所有元素，然后比较新元素和数组中每一个元素的大小，start取较小值，end取较大值，直到newInterval.end < intervals[i].start，然后拷贝剩余元素，很直观的方法vector<Interval> insert(vector<Interval>& intervals, Interval newInterval) vector<Interval> result; int i = 0; for(; i < intervals.size() && intervals[i].end < newInterval.start; i++) result.push_back(intervals[i]); for(; i < intervals.size() && intervals[i].start <= newInterval.end; i++) newInterval.start = min(newInterval.start, intervals[i].start); newInterval.end = max(newInterval.end, intervals[i].end); result.push_back(newInterval); for(; i < intervals.size(); i++) result.push_back(intervals[i]); return result;Recommend
-
77
问题描述： 有一个整形数组，包含正数和负数，然后要求把数组内的所有负数移至正数的左边，且保证相对位置不变，要求时间复杂度为O(n), 空间复杂度为O(1)。例如，{10, -2, 5, 8, -4, 2, -3, 7, 12, -88, -23, 35}变化后是{-2,...
-
29
原题 给定一个排序数组，你需要在原地删除重复出现的元素，使得每个元素最多出现两次，返回移除后数组的新长度。 不要使用额外的数组空间，你必须在原地修改输入数组并在使用 O(1) 额外空间的条件下完成。 ...
-
14
在排序数组中查找元素的第一个和最后一个位置 给定一个按照升序排列的整数数组 nums ，和一个目标值 target 。找出给定目标值在数组中的开始位置和结束位置。 如果数组中不存在目标值
-
15
力扣-1508 子数组和排序后的区间和
-
13
【LeetCode每日一题】33.搜索旋转排序数组.md 发表于...
-
8
26. 删除排序数组中的重复项 – Becomin' Charles跳至内容 Becomin' Charles Mac | Linux | 团队管...
-
2
为什么排序数组比未排序数组的处理速度要快? 今天在 Stack Overflow 上看到一个有趣的问题： Why is processing a sorted array faster than processing an unsorted array? 提问者列了一段代码： #include <algorithm&...
-
9
求无序数组排序后相邻俩数最大差值（思路及详解） | XINDOO 前两天在一个学长面试的时候遇到这样一个题，这里稍微详细说下本文的标题。给你ｎ个任意整数，求排序后相邻两个数之间的最大差值，这里n可能有10^5，整数为任意32位整型。要求求解算法的时间复杂度...
-
8
1. Javascript的 sort() 方法最常用最快的方法！定义：把数组按大小顺序排列@params：可以没有，也可以是函数@return：排好序后的数组是否改变原数组：改变使用方法：arr.sort()：SORT方法...
-
9
LeetCode 第 26 号问题：删除排序数组中的重复项-五分钟学算法 当前位置：五分钟学算法 > LeetCodeAnimation > LeetCode 第 26 号问题：删除排...
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK