Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

第 82 题:算法题「移动零」,给定一个数组 nums,编写一个函数将所有 0 移动到数组的末尾,同时保持非零元素的相对顺序。 #132

Open
yygmind opened this issue May 27, 2019 · 252 comments

Comments

@yygmind
Copy link
Contributor

yygmind commented May 27, 2019

示例:

输入: [0,1,0,3,12]
输出: [1,3,12,0,0]

说明:

  1. 必须在原数组上操作,不能拷贝额外的数组。

  2. 尽量减少操作次数。

@ChuYang-FE
Copy link

ChuYang-FE commented May 27, 2019

新增:解决了有连续的0无法实现功能的问题。

function zeroMove(array) {
        let len = array.length;
        let j = 0;
        for(let i=0;i<len-j;i++){
            if(array[i]===0){
                array.push(0);
                array.splice(i,1);
                i --;
                j ++;
            }
        }
        return array;
    }

@Rashomon511
Copy link

        const moveZore = (arr) => {
            let n = 0
            arr.forEach((item, index) => {
                if (item === 0){
                    arr.splice(index, 1)
                    n++;
                }
            })
            arr.push(...(new Array(n)).fill(0))
            return arr;
        }

@y1324
Copy link

y1324 commented May 27, 2019

let nums = [0,1,0,3,12];

for (let i = 0; i < nums.length; i++){
  if (nums[i] === 0){
    nums.push(0);
    nums.splice(i,1);
  }
};

@fengjinlong
Copy link

let arr = [1,2,3,0,7,0]
j = arr.length
for (i = 0; i < j; i++) {
if (arr[i] === 0) {
arr.splice(i,1)
arr.push(0)
}
}

@btea
Copy link

btea commented May 27, 2019

function move(arr){ 
  var n = 0; 
  for(var i = 0; i < arr.length; i++){ 
    if(arr[i] === 0){ 
       arr.splice(i, 1);
       n++; 
       i--; 
    }
  } 
  while(n--){ 
    arr.push(0); 
  }
  return arr;
}

@wingmeng
Copy link

wingmeng commented May 27, 2019

已修正连续多个 0 时的 bug
思路:用一个 len 记录 0 的出现次数,再过滤掉原数组中所有的 0,最后在数组末尾补上被移除的 0

let nums = [0, 0, 0, 1, 0, 3, 12];

console.log(moveZeroToLast(nums));  // [1, 3, 12, 0, 0, 0, 0]

function moveZeroToLast(arr) {
  let len = arr.length;

  return arr.filter(it => it === 0 ? len-- && false : true)
    .concat(Array(arr.length - len).fill(0));
}

@jjeejj
Copy link
Contributor

jjeejj commented May 27, 2019

上面所有的再循环中,先 splice 在 push 的方法都是有问题的

因为,当splice 一个元素的时候,紧跟着的后面一个元素会向前移动一位,索引会变成正在删除那个元素的,所有当有连续的 0 时候,无法满足要求

@wz71014q
Copy link

wz71014q commented May 27, 2019

const array = [2, 0, 1, 4, 0, 0, 0, 5, 7, 8];
array.sort((fir, sec) => {
  return fir === 0;
})
// array = [ 2, 1, 4, 5, 7, 8, 0, 0, 0, 0 ]

这里有个问题,首元素为0无效,不知道为什么,求教

const array = [0, 2, 0, 1, 4, 0, 0, 0, 5, 7, 8];
array.sort((fir, sec) => {
  return fir === 0;
})
console.log(array);
// array = [ 8, 7, 1, 4, 2, 5, 0, 0, 0, 0, 0 ]

@Hunterang
Copy link

let moveZero = (arr) => {
let point = 0
for (var i = 0; i < arr.length; i++) {
if (arr[i]!=0) {
arr[point] = arr[i]
arr[i] = 0
point++
}
}

return arr
}

@tanggd
Copy link

tanggd commented May 27, 2019

最优解法

想到好几个方法,楼上都写出来了,但是我觉得这些都不是最优解法,既然是算法题,自然是以算法的思维去解。

function moveZeroToLast(arr) {
    let index = 0;
    for (let i = 0, length = arr.length; i < length; i++) {
        if (arr[i] === 0) {
            index++;
        } else if (index !== 0) {
            arr[i - index] = arr[i];
            arr[i] = 0;
        }
    }
    return arr;
}

@y1324
Copy link

y1324 commented May 27, 2019

上面所有的再循环中,先splice在推的方法都是有问题的

因为,当splice一个元素的时候,紧跟着的后面一个元素会向前移动一位,索引会变成正在删除那个元素的,所有当有连续的​​0时候,无法满足要求

那个这个问题怎么解决?没头绪

@wheatma
Copy link

wheatma commented May 27, 2019

const moveZeroToEnd = (arr) => {
    let index = 0
    let current = 0
    while(index < arr.length) {
        if (arr[current] === 0) {
            arr.splice(current, 1)
            arr.push(0)
        } else {
            current++
        }
        index++
    }
    return arr
}

@moorain
Copy link

moorain commented May 27, 2019

//倒序循环可避免
const arr = [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 2, 3, 0, 0, 0, 1, 9, 9, 9, 0, 0, 0, 0, 1, 0, 3, 12, 0, 0, 0, 0];
    const len = arr.length;
    console.log(len)
    for (let i = len; i >= 0; i--) {
      if (arr[i] === 0) {
        arr.splice(i, 1);
        arr.push(0)
      }
    }
    console.log(arr)

@y1324
Copy link

y1324 commented May 27, 2019

//倒序循环可避免
const arr = [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 2, 3, 0, 0, 0, 1, 9, 9, 9, 0, 0, 0, 0, 1, 0, 3, 12, 0, 0, 0, 0];
    const len = arr.length;
    console.log(len)
    for (let i = len; i >= 0; i--) {
      if (arr[i] === 0) {
        arr.splice(i, 1);
        arr.push(0)
      }
    }
    console.log(arr)

为什么倒序可以解决这个办法

@moorain
Copy link

moorain commented May 27, 2019

//倒序循环可避免
const arr = [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 2, 3, 0, 0, 0, 1, 9, 9, 9, 0, 0, 0, 0, 1, 0, 3, 12, 0, 0, 0, 0];
    const len = arr.length;
    console.log(len)
    for (let i = len; i >= 0; i--) {
      if (arr[i] === 0) {
        arr.splice(i, 1);
        arr.push(0)
      }
    }
    console.log(arr)

为什么倒序可以解决这个办法

因为待处理的数据索引没有变。https://www.jianshu.com/p/77247e9e1849

@ZodiacSyndicate
Copy link

ZodiacSyndicate commented May 27, 2019

  • 首先,题意是要在原地修改数组,那么sort,concat之类的纯函数方法就是行不通的了,因为是返回新的数组,而不是在原地修改
  • 其次,splice的时间复杂度是O(n),那么使用splice的算法的时间复杂度是O(n2),既然在写算法,那么就要寻求时间复杂度与空间复杂度最低的办法。

思路:双指针

  • 设定一个慢指针一个快指针,快指针每次+1, 当慢指针的值不等于0的时候也往后移动,当慢指针等于0并且快指针不等于0的时候,交换快慢指针的值,慢指针再+1
function moveZero(arr) {
  let i = 0
  let j = 0
  while (j < arr.length) {
    if (arr[i] !== 0) {
      i++
    } else if (arr[j] !== 0) {
      ;[arr[i], arr[j]] = [arr[j], arr[i]]
      i++
    }
    j++
  }
}

时间复杂度O(n),n是数组长度,空间复杂度O(1)

@FruitPineapple
Copy link

//最后有啥办法不循环么,直接截取放最后
var arr = [0,1,0,3,12,0,89,0,8,0] ;

function ss (arr){
    arr.sort((a,b)=>{
        return a-b
    });
    let len = arr.lastIndexOf(0) +1;
    arr.splice(0,len);
    for (let i=0;i<len;i++){
        arr.push(0)
    }
    console.log(arr)
}
ss(arr)

@YouziXR
Copy link

YouziXR commented May 27, 2019

// 正序循环方案
// 由于splice会将nums.length - 1,所以让数组下标自减,强制回溯到上一个已操作的元素
const moveZeroToEnd = (nums) => {
	let length = nums.length
	for (let i = 0; i < nums.length; i++) {
		let el = nums[i]
		if (el === 0) {
			nums.splice(i, 1)
			i--
		}
	}
	let tmpAry = new Array((length - nums.length)).fill(0)
	return [...nums, ...tmpAry]
}
moveZeroToEnd([1,2,0,0,0,0,0,0,3,0,4])

@JayZangwill
Copy link

JayZangwill commented May 27, 2019

思路是把0剔除出来,然后再塞进去- -

function moveZero(arr) {
      let num = 0
      let index = -1
      while ((index = arr.indexOf(0)) > -1) {
        num++
        arr.splice(index, 1)
      }

      while (num--) {
        arr.push(0)
      }
}

@18692959234
Copy link

let or = [0, 1, 0, 3, 12]
let len = or.length
while (len) {
if(!or[len-1]){
or.push(...or.splice(len-1,1))
}
len --
}
console.log(or) // [1, 3, 12, 0, 0]

@lentoo
Copy link

lentoo commented May 27, 2019

function move (arr) {
let counter = 0
for (let index = 0; index < arr.length; index++) {
const item = arr[index];
if (item === 0) {
arr.splice(index, 1)
counter++
index--
}
}
arr.push(...new Array(counter).fill(0))
return arr
}

@TNTrocket
Copy link

function sortArr(arr) {
    let arrLength = arr.length;
    for (let i = 0; i < arrLength; i++) {
      if (arr[i] === 0) {
        arr.splice(i, 1);
        i--;
        arrLength--;
        arr.push(0);
      }
    }
    return arr;
  }

@lo1412
Copy link

lo1412 commented May 27, 2019

 function moveZero(arr) {
        if (!arr instanceof Array || arr.length <= 0) return arr
        let zeroIndex = -1;
        let i = 0;
        while (i < arr.length) {
            if (arr[i] !== 0 && zeroIndex >= 0) {
                swap(i, zeroIndex, arr)
                zeroIndex++
            } else if (arr[i] === 0 && zeroIndex < 0) {
                zeroIndex = i
            }
            i++
        }
        return arr
    }

    function swap(i, j, arr) {
        [arr[i], arr[j]] = [arr[j], arr[i]]
    }
    const arr = [0, 1, 0, 3, 12]
    console.log(moveZero(arr))

原地交换,没有用多余的数组。应该是O(n)。
木有上面大佬的简洁,不知道能不能覆盖所有情况,求指正

@kingstone3
Copy link

const array = [2, 0, 1, 4, 0, 0, 0, 5, 7, 8];
array.sort((fir, sec) => {
  return fir === 0;
})
// array = [ 2, 1, 4, 5, 7, 8, 0, 0, 0, 0 ]

这里有个问题,首元素为0无效,不知道为什么,求教

const array = [0, 2, 0, 1, 4, 0, 0, 0, 5, 7, 8];
array.sort((fir, sec) => {
  return fir === 0;
})
console.log(array);
// array = [ 8, 7, 1, 4, 2, 5, 0, 0, 0, 0, 0 ]

这个我在 chrome 上试的时候无法排序,在 safari 上倒是可以按照逻辑输出 @wz71014q

@jjeejj
Copy link
Contributor

jjeejj commented May 27, 2019

上面所有的再循环中,先splice在推的方法都是有问题的
因为,当splice一个元素的时候,紧跟着的后面一个元素会向前移动一位,索引会变成正在删除那个元素的,所有当有连续的​​0时候,无法满足要求

那个这个问题怎么解决?没头绪

还用上面的方法的话,如果元素为0,可以把正在循环的索引减 1

@lo1412
Copy link

lo1412 commented May 27, 2019

const array = [2, 0, 1, 4, 0, 0, 0, 5, 7, 8];
array.sort((fir, sec) => {
  return fir === 0;
})
// array = [ 2, 1, 4, 5, 7, 8, 0, 0, 0, 0 ]

这里有个问题,首元素为0无效,不知道为什么,求教

const array = [0, 2, 0, 1, 4, 0, 0, 0, 5, 7, 8];
array.sort((fir, sec) => {
  return fir === 0;
})
console.log(array);
// array = [ 8, 7, 1, 4, 2, 5, 0, 0, 0, 0, 0 ]

这个我在 chrome 上试的时候无法排序,在 safari 上倒是可以按照逻辑输出 @wz71014q

const array = [0, 2, 0, 1, 4, 0, 0, 0, 5, 7, 8];
array.sort((fir, sec) => {
return (fir === 0) ? 1 : -1
})

这样试试?

如果想按照其他标准进行排序,就需要提供比较函数,该函数要比较两个值,然后返回一个用于说明>这两个值的相对顺序的数字。比较函数应该具有两个参数 a 和 b,其返回值如下:

若 a 小于 b,在排序后的数组中 a 应该出现在 b 之前,则返回一个小于 0 的值。
若 a 等于 b,则返回 0。
若 a 大于 b,则返回一个大于 0 的值。

@kingstone3
Copy link

kingstone3 commented May 27, 2019

可以了,谢啦 @lo1412

@HduSy
Copy link

HduSy commented May 27, 2019

clock in

@Nolaaaaa
Copy link

Nolaaaaa commented May 27, 2019

思路:

  1. 先把数组中的0全部去掉
  2. 对比初始数组和去掉0后的数组的长度
  3. 长度相差多少就在数组末尾添加几个0
const result = (arr) => arr.filter(Boolean).concat([...Array(arr.length - arr.filter(Boolean).length).fill(0)])
result([0,1,0,3,0,12,0])    // [1, 3, 12, 0, 0, 0, 0]

@wz71014q
Copy link

@kingstone3 我用node运行的是可以,后面放到chrome果然结果不一样。。。没有safari。。。没有试具体结果

// 换成这样后,在chrome第一次是输出全部相反的顺序,再运行一次sort,才会把顺序变回来
const array = [0, 2, 0, 1, 4, 0, 0, 0, 5, 7, 8];
array.sort((fir, sec) => {
    return (fir === 0) ? 1 : -1
})

@shizhouyu
Copy link

shizhouyu commented Oct 27, 2022 via email

@Stephen-Monster
Copy link

Stephen-Monster commented Oct 27, 2022 via email

@xuhen
Copy link

xuhen commented Nov 29, 2022

function moveZero(arr) {
    let i = 0;
    let j = 0;
    const len = arr.length;
    while (i < len - j) {
        if (arr[i] === 0) {
            const item = arr.splice(i, 1);
            arr.push(...item);
            j++;
        } else {
            i++;
        }
    }

    return arr;
}

@shizhouyu
Copy link

shizhouyu commented Nov 29, 2022 via email

@Stephen-Monster
Copy link

Stephen-Monster commented Nov 29, 2022 via email

@benzhemin
Copy link

const moveZeroEnd = numList => {

    const end = numList.length;

    for (let i = 0, cursor = 0 ;i < end; i++) {
        if (cursor >= end) {
            numList[i] = 0;
            continue;
        }

        for (; cursor < end && numList[cursor] === 0; cursor++);

        numList[i] = numList[cursor];
        cursor++;
    }
}

const inputList = [0,1,0,3,12];

moveZeroEnd(inputList);
console.log(inputList);

const inputList1 = [0, 0, 0, 0, 1, 2, 3, 0, 4];
moveZeroEnd(inputList1);
console.log(inputList1);

@shizhouyu
Copy link

shizhouyu commented Feb 25, 2023 via email

@Stephen-Monster
Copy link

Stephen-Monster commented Feb 25, 2023 via email

@18679850773
Copy link

18679850773 commented Feb 28, 2023 via email

@shawn-play
Copy link

shawn-play commented Mar 13, 2023

答案中有很多用到splice, 其实是不太符合题意的,毕竟一个splice会移动所有0后面的数字。
这里的思路是冒泡,[0, 1]的情况一次移动得到[1,0], 同理[1,0,0,0,4] 经过[arr[1], arr[4]] = [arr[4], arr[1]]一次移动,可获得[1,4,0,0,0], 这样可以保证最小的移动次数,同时保证了性能

function bubble(arr) {
  const len = arr.length;
  for(let i = 0, step = 1; i + step < len;) {
    let j = i + step;
    if (arr[i] === 0) {
      if (arr[j] !== 0) {
        [arr[i], arr[j]] = [arr[j], arr[i]]
        i++
      } else {
        step ++
      }
    } else {
      i++
    }
  }
  console.log(arr)
}

bubble([12,4,8,0,9,78,67,0,45,98,33,00,23,767,8878,66,90,-87,8,0,67,65])

@luke358
Copy link

luke358 commented Mar 13, 2023

插入排序原理

function moveZeroToEnd(arr) {
  let len = arr.length;

  for (let i = len - 2; i >= 0; i--) {
    let tmp = arr[i]
    let j = i + 1;
    while ((j < len) && tmp === 0) {
      arr[j - 1] = arr[j]
      j++;
    }
    arr[j - 1] = tmp
    console.log(arr);
  }
  return arr
}

@jean-Val-jean-j
Copy link

    arr.forEach((item,index)=>{
        if(item===0){
            arr.push(arr.splice(index,1)[0])
        }
    })

@shizhouyu
Copy link

shizhouyu commented Mar 29, 2023 via email

@Stephen-Monster
Copy link

Stephen-Monster commented Mar 29, 2023 via email

@chthu
Copy link

chthu commented Apr 11, 2023

const moveToEnd = (arr) => {
for (let i = arr.length; i >= 0; i--) {
if (arr[i] === 0) {
arr.push(...arr.splice(i, 1))
}
}
return arr
}

@qifengla
Copy link

function moveZeroes(nums) {
  const len = nums.length;
  let left = 0;
  
  for (let right = 0; right < len; right++) {
    if (nums[right] !== 0) {
      nums[left] = nums[right];
      left++;
    }
  }
  
  for (let i = left; i < len; i++) {
    nums[i] = 0;
  }
}

const nums = [0, 1, 0, 3, 12];
moveZeroes(nums);
console.log(nums);

@shizhouyu
Copy link

shizhouyu commented May 31, 2023 via email

@Stephen-Monster
Copy link

Stephen-Monster commented May 31, 2023 via email

@88wixi
Copy link

88wixi commented Jul 24, 2023

let arr = [0, 1, 0, 3, 12, 0, 9, 8, 6, 0, 1]
function changeArea(arr) {
arr.forEach((element, index) => {
if (element === 0) {
for (i = index; i < arr.length - 1; i++) {
let temp
temp = arr[i]
arr[i] = arr[i + 1]
arr[i + 1] = temp
}
}
});
}
changeArea(arr)
console.log(arr)

@shizhouyu
Copy link

shizhouyu commented Jul 24, 2023 via email

@Stephen-Monster
Copy link

Stephen-Monster commented Jul 24, 2023 via email

@wut1
Copy link

wut1 commented Aug 12, 2023

let len = nums.length
let i = 0
let max = len
while(i < max){
if(nums[i] === 0){
nums.splice(i,1)
nums.push(0)
max--
} else {
i++
}

}
return nums

@shizhouyu
Copy link

shizhouyu commented Aug 12, 2023 via email

@Stephen-Monster
Copy link

Stephen-Monster commented Aug 12, 2023 via email

@shizhouyu
Copy link

shizhouyu commented Nov 3, 2023 via email

@Stephen-Monster
Copy link

Stephen-Monster commented Nov 3, 2023 via email

@xiguahuibaozha
Copy link

[0, 1, 0, 3, 12, 0, 9, 8, 6, 0, 1].sort((a,b) => { if(b){ return 0 }else { return -1 } })

@MyPrototypeWhat
Copy link

一个循环就结束 很简单

const fn = (arr) => {
  let count = 0;
  for (let i in arr) {
    if (arr[i] === 0) {
      count++;
    } else {
      arr[i - count] = arr[i];
      arr[i] = 0;
    }
  }
};

@shizhouyu
Copy link

shizhouyu commented Jun 3, 2024 via email

@Stephen-Monster
Copy link

Stephen-Monster commented Jun 3, 2024 via email

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Projects
None yet
Development

No branches or pull requests