📣 黑五价提前开抢|VIP一年通行证5折,蓝莓、Offer多多同步特惠
楼主: wwwyhx
跳转到指定楼层
上一主题 下一主题
收起左侧

Microsoft : Sort 只含0,1,2三个元素的数组

 
🔗
dearmiles 2013-12-11 21:30:07 | 只看该作者
全局:
不太明白有啥要求。。复杂度,输入输出?
题目没给全吧。

O(n)的算法都有很多种啊。
知道最大值最小值,对定长数组排序...有啥更加无聊的嘛
回复

使用道具 举报

🔗
GTea 2013-12-15 08:22:25 | 只看该作者
全局:
这个和leetcode上的sort colors是一样的。

我的代码:
  1. public class Solution {
  2.     public void sortColors(int[] A) {
  3.        if (A == null || A.length == 0) {
  4.            return;
  5.        }
  6.       
  7.        int i = 0;
  8.        int m = 0;
  9.        int j = A.length - 1;
  10.        while (m <= j) { // while (m < j) {
  11.            if (A[m] < 1) {
  12.                swap(A, i, m);
  13.                i++;
  14.                m++;
  15.            }
  16.            else if (A[m] > 1) {
  17.                swap(A, m, j);
  18.                j--;
  19.                // m++;
  20.            }
  21.            else {
  22.                m++;
  23.            }
  24.        }
  25.     }
  26.    
  27.     private void swap(int[] A, int a, int b) {
  28.         if (A == null || a < 0 || a >= A.length || b < 0 || b >= A.length) {
  29.             return;
  30.         }
  31.         
  32.         int temp = A[a];
  33.         A[a] = A[b];
  34.         A[b] = temp;
  35.     }
  36. }
复制代码


回复

使用道具 举报

🔗
bolun 2013-12-21 18:34:45 | 只看该作者
全局:
8楼 9楼+1!
回复

使用道具 举报

🔗
arycn 2013-12-23 07:16:40 | 只看该作者
全局:
本帖最后由 arycn 于 2013-12-23 07:17 编辑

用三个指针lo,mid,hi, 划分四个区域,0,1,2,和unknown。整个算法就是个缩小unknown区域的过程。
void sort012(int a[], int arr_size)
{
   int lo = 0;
   int hi = arr_size - 1;
   int mid = 0;

   while(mid <= hi)
   {
      switch(a[mid])
      {
         case 0:
           swap(&a[lo++], &a[mid++]);
           break;
         case 1:
           mid++;
           break;
         case 2:
           swap(&a[mid], &a[hi--]);
           break;
      }
   }
回复

使用道具 举报

🔗
gu0001hi 2013-12-23 12:40:09 | 只看该作者
全局:
leetcode有一样的题目,是sort color,很巧妙的解法,用了3个指针,1pass解决。
回复

使用道具 举报

🔗
gu0001hi 2013-12-23 12:40:57 | 只看该作者
全局:
class Solution {
public:
    void sortColors(int A[], int n) {
        if(n<=1)
            return;
        int a1 = 0;
        int a2= n-1;
        int a3 = n-1;
        while(a1<=a2)
        {
            if(A[a1]==0)
            {
                a1++;
                continue;
            }
            if(A[a1] ==2)
            {
                A[a1] = A[a3];
                A[a3--] = 2;
                if(a2>a3)
                    a2 = a3;
                continue;
            }
            if(A[a1] == 1)
            {
                A[a1] = A[a2];
                A[a2--] = 1;
                continue;
            }
            
        }
    }
};
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 注册账号
隐私提醒:
  • ☑ 禁止发布广告,拉群,贴个人联系方式:找人请去🔗同学同事飞友,拉群请去🔗拉群结伴,广告请去🔗跳蚤市场,和 🔗租房广告|找室友
  • ☑ 论坛内容在发帖 30 分钟内可以编辑,过后则不能删帖。为防止被骚扰甚至人肉,不要公开留微信等联系方式,如有需求请以论坛私信方式发送。
  • ☑ 干货版块可免费使用 🔗超级匿名:面经(美国面经、中国面经、数科面经、PM面经),抖包袱(美国、中国)和录取汇报、定位选校版
  • ☑ 查阅全站 🔗各种匿名方法

本版积分规则

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