📣 VIP通行证夏日特惠 限时立减$68
楼主: goodgoodstudy
跳转到指定楼层
上一主题 下一主题
收起左侧

fb 电面挂经

🔗
sunfish 2017-4-9 04:13:18 | 只看该作者
全局:
如果数学可以重复用的话,那最坏复杂度是 n^3吧?
回复

使用道具 举报

🔗
scredwood 2017-4-9 05:50:15 | 只看该作者
全局:
say543 发表于 2017-4-8 13:38
lz move zero 那堤能说说怎做吗? 一直没找到answer...

two pointer
  1. left = 0, right = arr.length -1

  2. while (left < right) {
  3.     while (left < right && arr[left] != 0) left++;
  4.     while (left < right && arr[right] == 0) right --;

  5.     if (left < right) {
  6.        swap(arr, left, right);
  7.        left++,  right --;
  8.     }
  9. }
复制代码
回复

使用道具 举报

🔗
scredwood 2017-4-9 05:55:22 | 只看该作者
全局:

move 最少的话,不要用这种办法。还有一种解法。要看题目要求,如果不用管后面的数字可以。
因为一个swap算移动两次,如果我们这样copy的话,每个0只要移动一次。
  1. index = 0;
  2. for (int i = 0; i < arr.length; i++) {
  3.     if (arr[i] != 0) {
  4.         arr[index++] = arr[i];
  5.     }
  6. }
复制代码
回复

使用道具 举报

全局:
scredwood 发表于 2017-4-9 05:55
move 最少的话,不要用这种办法。还有一种解法。要看题目要求,如果不用管后面的数字可以。
因为一个swa ...

这个感觉算不上move最少。
即便是要考虑保持原来的顺序,你这里也最好加个判断 index!=i 再移动
回复

使用道具 举报

全局:
sean1993519 发表于 2017-4-9 03:56
哈哈对对,脑抽了,光想着用map存index了,用array存确实好一点,请问一下最好的方法这么做是建个compara ...

是呀  应该是的
回复

使用道具 举报

🔗
scredwood 2017-4-9 11:07:18 | 只看该作者
全局:
翻滚吧豆子 发表于 2017-4-9 07:22
这个感觉算不上move最少。
即便是要考虑保持原来的顺序,你这里也最好加个判断 index!=i 再移动

不然还能怎么少哇。

回复

使用道具 举报

全局:
scredwood 发表于 2017-4-9 11:07
不然还能怎么少哇。

不保持原顺序的情况下,双指针是最少
回复

使用道具 举报

🔗
sean1993519 2017-4-10 03:37:50 | 只看该作者
全局:
求问如果要保留非0的顺序,是不是下面的方法比较好
  1. public void moveZeroes(int[] nums) {
  2.         int zeropos = 0;
  3.         for (int curpos = 0; curpos < nums.length; curpos++) {
  4.             if(nums[curpos] != 0 && zeropos != curpos){
  5.                 nums[zeropos++] = nums[curpos];
  6.             }else if (nums[curpos] != 0 && zeropos == curpos){
  7.                 zeropos++;
  8.             }
  9.         }
  10.         while(zeropos < nums.length){
  11.             nums[zeropos++] = 0;
  12.         }
  13.     }
复制代码
回复

使用道具 举报

🔗
smallwarm 2017-4-10 06:00:27 | 只看该作者
全局:
sean1993519 发表于 2017-4-10 03:37
求问如果要保留非0的顺序,是不是下面的方法比较好

对,挺好了
回复

使用道具 举报

🔗
badweather 2017-4-11 09:06:48 | 只看该作者
全局:
谢谢分享!楼主好运!
回复

使用道具 举报

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

本版积分规则

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