找回密码
 立即注册

QQ登录

只需一步,快速开始

扫一扫,访问微社区

查看: 3772|回复: 11
收起左侧

[米群网刷题小分队] [LeetCode] Array 题目

[复制链接]

90

主题

46

精华

1908

积分

版主

Rank: 7Rank: 7Rank: 7

积分
1908

热心会员突出贡献优秀版主最佳新人精华帖之王活跃会员

发表于 12-11-2014 02:24 AM | 显示全部楼层 |阅读模式

亲!马上注册或者登录会查看更多内容!

您需要 登录 才可以下载或查看,没有帐号?立即注册

x
本帖最后由 MengMa 于 12-12-2014 07:51 PM 编辑

Merge Interval


时间复杂度 O(nlogn + n) -> O(nlogn), 空间复杂度 O(1)
  1. public class Solution {
  2.     public ArrayList<Interval> merge(ArrayList<Interval> intervals)
  3.     {
  4.         ArrayList<Interval> res = new ArrayList<Interval>();
  5.         if(intervals == null || intervals.size() == 0) return intervals;
  6.         Comparator<Interval> comp = new Comparator<Interval>()
  7.         {
  8.             @Override
  9.             public int compare(Interval i1, Interval i2)
  10.             {
  11.                 if(i1.start == i2.start)
  12.                     return i1.end - i2.end;
  13.                 return i1.start - i2.start;
  14.             }
  15.         };
  16.         Collections.sort(intervals, comp);
  17.         res.add(intervals.get(0));
  18.         for(int i = 1; i < intervals.size(); i++)
  19.         {
  20.             if(res.get(res.size() - 1).end >= intervals.get(i).start)
  21.                 res.get(res.size() - 1).end = Math.max(res.get(res.size() - 1).end, intervals.get(i).end);
  22.             else
  23.                 res.add(intervals.get(i));
  24.         }
  25.         return res;
  26.     }
  27. }
复制代码





Insert Interval
按照cpcs的思路,做了个java版本。时间复杂度 O(n) 空间复杂度,算上结果的空间是O(n)

  1. public class Solution {
  2.     public ArrayList<Interval> insert(ArrayList<Interval> intervals, Interval newInterval)
  3.     {
  4.         ArrayList<Interval> res = new ArrayList<Interval>();
  5.         if(intervals.size() == 0){
  6.             res.add(newInterval);
  7.             return res;
  8.         }
  9.         int i;
  10.         for(i = 0; (i < intervals.size()) && (intervals.get(i).start <= newInterval.start); ++i)
  11.         {
  12.             if(intervals.get(i).end >= newInterval.start)
  13.             {
  14.                 newInterval.start = intervals.get(i).start;
  15.                 newInterval.end = Math.max(newInterval.end, intervals.get(i).end);
  16.             }
  17.             else
  18.                 res.add(intervals.get(i));
  19.         }
  20.         for (; (i < intervals.size()) && (intervals.get(i).start <= newInterval.end); ++i) {
  21.             newInterval.end = Math.max(newInterval.end, intervals.get(i).end);
  22.         }
  23.         res.add(newInterval);
  24.         for (; i < intervals.size(); ++i) {
  25.             res.add(intervals.get(i));
  26.         }
  27.         return res;
  28.     }
  29. }
复制代码


First Missing Possitive
Surrounded Regions

本帖被以下淘专辑推荐:

90

主题

46

精华

1908

积分

版主

Rank: 7Rank: 7Rank: 7

积分
1908

热心会员突出贡献优秀版主最佳新人精华帖之王活跃会员

 楼主| 发表于 12-13-2014 09:57 PM | 显示全部楼层
First Missing Number

思路【wyu277】
既然是constant space 那就要好好利用这个数组的空间。
之前也提到排序,但是又不能用普通的sort。
那In-place sort 该怎么做呢?
其实,这题还有一个条件:
#(1 ~ A.length) 的positive integer 最多只有A.length个。
那我们只要把这些 在这个范围内的数 [放回] 他应该在的位置(sort后的位置)
A[index] 应该放 #(index+1)

second pass:扫一遍,看数组每格放的数是不是应该放的数,不是则返回应该放的那个数

时间O(n) 空间 O(1)
  1. public class Solution {
  2.     public int firstMissingPositive(int[] A) {
  3.         int len = A.length;
  4.         for(int i = 0; i < len; i++)
  5.         {
  6.             while(A【i】 != i + 1)
  7.             {
  8.                 if(A【i】 <= 0 || A【i】 >  len || A【i】 == A[A【i】 - 1]) break; //num k stores in kth position
  9.                 int tmp = A【i】; //A【i】 gets changed later
  10.                 A【i】 = A[tmp - 1];
  11.                 A[tmp - 1] = tmp;
  12.             }
  13.         }
  14.         for(int i = 0; i < A.length; i++)
  15.         {
  16.             if(A【i】 != i+1) return i + 1;
  17.         }
  18.         return A.length + 1;
  19.     }
  20. }
复制代码

90

主题

46

精华

1908

积分

版主

Rank: 7Rank: 7Rank: 7

积分
1908

热心会员突出贡献优秀版主最佳新人精华帖之王活跃会员

 楼主| 发表于 12-13-2014 11:02 PM | 显示全部楼层
Merge Sorted Arrays

从后往前搞。
  1. public class Solution {
  2.     public void merge(int A[], int m, int B[], int n) {
  3.        if(A==null || B==null)
  4.         return;
  5.         int indexA = m - 1 ;
  6.         int indexB = n - 1 ;
  7.         int end = m + n - 1;
  8.         while(indexA >= 0 && indexB >= 0)
  9.         {
  10.             if(A[indexA] > B[indexB])
  11.             {
  12.                 A[end--] = A[indexA--];
  13.             }
  14.             else if (A[indexA] <= B[indexB])
  15.             {
  16.                 A[end--] = B[indexB--];
  17.             }
  18.         }
  19.         while(indexB >= 0)
  20.         A[end --] = B[indexB --];
  21.         return;
  22.     }
  23. }
复制代码


您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

快速回复 返回顶部 返回列表