↓ Skip to main content
111qqz’s blog
  1. Posts/

leetcode 442. Find All Duplicates in an Array（找出出现两次的元素）

·1 min
面试 Leetcode
Note: This article is available in Chinese only. 本文暂无英文版本。 View original

Given an array of integers, 1 ≤ a[i] ≤ n (n = size of array), some elements appear twice and others appear once.

Find all the elements that appear twice in this array.

Could you do it without extra space and in O(n) runtime?

思路：还是一个映射，如果某个位置要映射的时候已经为负了，就说明之前映射过该位置，那么该位置对应的元素就是出现了两个的元素。

和leetcode 448是一对题目。

 1/* ***********************************************
 2Author :111qqz
 3Created Time :2017年04月12日 星期三 21时49分11秒
 4File Name :442.cpp
 5************************************************ */
 6class Solution {
 7
 8public:
 9
10    vector<int> findDuplicates(vector<int>& nums) {
11    vector<int>res;
12    int n = nums.size();
13    if (n==0) return res;
14    for ( int i = 0 ; i < n ; i++)
15    {
16        int id = abs(nums[i])-1;
17//      printf("%d%c",id,i==n-1?'\n':' ');
18        if (nums[id]>0)nums[id] *=-1;
19        else res.push_back(id+1);
20    }
21//  for ( int i = 0 ; i< n ;i++) printf("%d%c",nums[i],i==n-1?'\n':' ');
22    return res;
23
24    }
25
26};

Related

leetcode 55. Jump Game (dp)

·1 min
面试 Leetcode
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]. 思路:dp[i]表示能否到达位置i…无脑dp即可。。。

leetcode 56. Merge Intervals (模拟，求相交区间)

·1 min
面试 Leetcode
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]. 思路：扫一遍即可。。 1/* *********************************************** 2Author :111qqz 3Created Time :2017年04月11日 星期二 19时15分30秒 4File Name :56.cpp 5************************************************ */ 6/** 7 8 * Definition for an interval. 9 10 * struct Interval { 11 12 * int start; 13 14 * int end; 15 16 * Interval() : start(0), end(0) {} 17 18 * Interval(int s, int e) : start(s), end(e) {} 19 20 * }; 21 22 */ 23 24class Solution { 25 26public: 27 28 int n; 29 static bool cmp(Interval A,Interval B) 30 { 31 return A.start<B.start; 32 } 33 vector<Interval> merge(vector<Interval>& pi) { 34 vector<Interval>res; 35 n = pi.size(); 36 if (n==0) return res; 37 sort(pi.begin(),pi.end(),cmp); 38 int l = -1,r = -1; 39 for ( int i = 0 ; i < n ; i++) 40 { 41 if (l==-1&&r==-1) 42 { 43 l = pi[0].start; 44 r = pi[0].end; 45 continue; 46 } 47 if (pi[i].start<=r) 48 { 49 r = max(r,pi[i].end); 50 continue; 51 } 52 if (pi[i].start>r) 53 { 54 res.push_back(Interval(l,r)); 55 l = pi[i].start; 56 r = pi[i].end; 57 continue; 58 } 59 } 60 //最后一组不要忘记 61 res.push_back(Interval(l,r)); 62 int siz = res.size(); 63 for ( int i = 0 ; i < siz ;i++) printf("%d ",res[i].start,res[i].end); 64 65 66 return res; 67 68 } 69 70};