首页

# 56. 合并区间

0 <= starti <= endi <= 104

下标都比较小，考虑直接存储

class Solution {
public:
	vector<vector<int>> merge(vector<vector<int>>& intervals) {
		int minIndex, maxIndex;
		minIndex = int(1e4 + 2), maxIndex = -1;
		for (vector<int>& interval : intervals) {
			minIndex = min(minIndex, interval[0]);
			maxIndex = max(maxIndex, interval[1]);
		}
		map<int, bool> mp;
		for (vector<int>& interval : intervals) {
			for (int i = interval[0]; i <= interval[1]; i++) {
				mp[i] = true;
			}
		}
		vector<int> ve;
		int index = minIndex;
		while (index <= maxIndex) {
			ve.push_back(index); // 记录一个区间的左端点
			while (mp[index] == true) {
				index++;  // 走遍区间
			}
			ve.push_back(index - 1);
			while (index <= maxIndex && mp[index] == false)
			{
				index++;
			}
		}
		vector<vector<int> > res;
		for (int i = 0; i < ve.size(); i += 2) {
			vector<int> temp;
			temp.push_back(ve[i]);
			temp.push_back(ve[i + 1]);
			res.push_back(temp);
		}
		return res;
	}
};
上面的解答是错误的，因为这是区间，不是点集合
class Solution {
public:
	vector<vector<int>> merge(vector<vector<int>>& intervals) {
		int minIndex, maxIndex;
		minIndex = int(1e4 + 2), maxIndex = -1;
		for (vector<int>& interval : intervals) {
			minIndex = min(minIndex, interval[0]);
			maxIndex = max(maxIndex, interval[1]);
		}
		map<int, pair<int, int> > mp;
		for (vector<int>& interval : intervals) {
			for (int i = interval[0]; i <= interval[1]; i++) {
				if (mp.find(i) == mp.end()) {
					mp[i] = pair<int, int>{ interval[0], interval[1] };
				}
				else {
					int l = min(mp[i].first, interval[0]);
					int r = max(mp[i].second, interval[1]);
					//l 和 r 还需要继续更新
					// 之前的也要更新
					for (int j = l; j <= r; j++) {
						if (mp.find(j) != mp.end())
							mp[j] = pair<int, int>{ min(l, mp[j].first), max(r, mp[j].second) };
						else
							mp[j] = pair<int, int>{ l, r };
					}
                    // 这里没有用 break，就会导致复杂度会比较高
                    // 即使没有用 break，遍历区间内的所有整数点，都会导致复杂度比较高
				}
			}
		}
		vector<int> ve;
		int index = minIndex;
		vector<vector<int> > res;
		//map 的遍历不一定是顺序的，
		for (int i = minIndex; i <= maxIndex;) {
			res.push_back({ mp[i].first, mp[i].second });
			// 走过相同的
			i++;
			while (mp.find(i) != mp.end() && mp[i] == mp[i-1]) {
				i++;
			}
			// 走过不在区间内的
			while (i <= maxIndex && mp.find(i) == mp.end()) {
				i++;
			}
		}
		
		return res;
	}
};
1710516388321
复杂度降不下来了，原因应该是反复循环更新的问题。
下面优化了下，就能通过了，但是效果不是很理想
class Solution {
public:
	vector<vector<int>> merge(vector<vector<int>>& intervals) {
		int minIndex, maxIndex;
		minIndex = int(1e4 + 2), maxIndex = -1;
		for (vector<int>& interval : intervals) {
			minIndex = min(minIndex, interval[0]);
			maxIndex = max(maxIndex, interval[1]);
		}
		map<int, pair<int, int> > mp;
		for (vector<int>& interval : intervals) {
			for (int i = interval[0]; i <= interval[1]; i++) {
				if (mp.find(i) == mp.end()) {
					mp[i] = pair<int, int>{ interval[0], interval[1] };
				}
				else {
					int l = min(mp[i].first, interval[0]);  // 这个确实是最小值，
					int r = max(mp[i].second, interval[1]); // 这个当前可能还不是最大值，因为 interval [0] 可能处在左边的一个区间中，到 interval [1] 可能又到了右边的区间
					for (int j = i + 1; j <= interval[1]; j++) {
						if (mp.find(j) != mp.end())
							r = max(r, mp[j].second);
					}
					//l 和 r 还需要继续更新，此时
					// 之前的也要更新
					for (int j = l; j <= r; j++) {
						if (mp.find(j) != mp.end())
							mp[j] = pair<int, int>{ min(l, mp[j].first), max(r, mp[j].second) };
						else
							mp[j] = pair<int, int>{ l, r };
					}
					break;
				}
			}
		}
		vector<int> ve;
		int index = minIndex;
		vector<vector<int> > res;
		//map 的遍历不一定是顺序的，
		for (int i = minIndex; i <= maxIndex;) {
			res.push_back({ mp[i].first, mp[i].second });
			// 走过相同的
			i++;
			while (mp.find(i) != mp.end() && mp[i] == mp[i-1]) {
				i++;
			}
			// 走过不在区间内的
			while (i <= maxIndex && mp.find(i) == mp.end()) {
				i++;
			}
		}
		
		return res;
	}
};
struct interval {
	int left;
	int right;
	interval(int left, int right) {
		this->left = left;
		this->right = right;
	}
};
bool cmp(interval& a, interval& b) {
	if (a.left < b.left)
		return true;
	else if (a.left == b.left)
		return a.right < b.right;
	else
		return false;
}
class Solution {
public:
	vector<vector<int>> merge(vector<vector<int>>& intervals) {
		vector<interval> ve;
		
		for (auto& a : intervals) {
			ve.push_back(interval(a[0], a[1]));
		}
		sort(ve.begin(), ve.end(), cmp);
		vector<vector<int> > res;
		for (auto& a : ve) {
			if (res.size() == 0)
				res.push_back({ a.left, a.right });
			else {
				int index = res.size() - 1;
				if (res[index][1] >= a.left && res[index][1] < a.right) {
					res[index][1] = a.right;
				}
				else if (res[index][1] < a.left) {
					res.push_back({ a.left, a.right });
				}
			}
		}
		return res;
	}
};
下面的官方解答好简洁
class Solution {
public:
    vector<vector<int>> merge(vector<vector<int>>& intervals) {
        if (intervals.size() == 0) {
            return {};
        }
        sort(intervals.begin(), intervals.end());
        vector<vector<int>> merged;
        for (int i = 0; i < intervals.size(); ++i) {
            int L = intervals[i][0], R = intervals[i][1];
            if (!merged.size() || merged.back()[1] < L) {
                merged.push_back({L, R});
            }
            else {
                merged.back()[1] = max(merged.back()[1], R);
            }
        }
        return merged;
    }
};
# 189. 轮转数组
class Solution {
public:
	void rotate(vector<int>& nums, int k) {
		
        if(k % nums.size() == 0)
            return;
        else {
            k = k % nums.size();
        }
        
        int index = nums.size() - k;

		vector<int> res;

		for (int i = index; i < nums.size(); i++) {
			res.push_back(nums[i]);
		}

		for (int i = 0; i < index; i++) {
			res.push_back(nums[i]);
		}
		nums = res;
	}
};

# 41. 缺失的第一个正数
class Solution {
public:
	int firstMissingPositive(vector<int>& nums) {
		sort(nums.begin(), nums.end());
		int res = 1;
		for (int& num : nums) {
			if (num < res) {
				continue;
			}
			else if (num == res) {
				res++;
			}
			else {
				break;
			}
		}
		return res;
	}
};
class Solution {
public:
	int firstMissingPositive(vector<int>& nums) {
		int N = nums.size();
		for (int& num : nums) {
			if (num <= 0) {
				num = N + 1;
			}
		}
		for (int i = 0; i < nums.size(); i++) {
			int num = abs(nums[i]);
			if (1 <= num && num <= N && nums[num-1] > 0) {
				nums[num - 1] = -nums[num - 1];
			}
		}
		for (int i = 0; i < N; i++) {
			if (nums[i] > 0) {
				return i + 1;
			}
		}
		return N + 1;
	}
};
class Solution {
public:
	int firstMissingPositive(vector<int>& nums) {
		int N = nums.size();
		for (int i = 0; i < nums.size(); i++) {
			
			while (nums[i] != i + 1 && 1 <= nums[i] && nums[i] <= N) {
				int x = nums[i];
                if(nums[i] != nums[x - 1]){
				    swap(nums[i], nums[x - 1]);
                }else{
                    break;
                }
			}
		}
		for (int i = 0; i < N; i++) {
			if (nums[i] != i + 1) {
				return i + 1;
			}
		}
		return N + 1;
	}
};
  • 为什么使用置换方法的时候得需要循环，不能够逐个遍历逐个置换么？
  • 这里就是逐个遍历替换的，当 i 较大的时候，是可以改变数组先前遍历过的位置上的值的。逐个遍历的时候，相当于访问了数组中的每一个元素了，并把每一个元素送到它应该到的位置上去。