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

第 77 题:旋转数组算法题 #126

Open
ZodiacSyndicate opened this issue May 20, 2019 · 136 comments
Open

第 77 题:旋转数组算法题 #126

ZodiacSyndicate opened this issue May 20, 2019 · 136 comments

Comments

@ZodiacSyndicate
Copy link

ZodiacSyndicate commented May 20, 2019

因为步数有可能大于数组长度,所以要先取余

function rotate(arr, k) {
  const len = arr.length
  const step = k % len
  return arr.slice(-step).concat(arr.slice(0, len - step))
}
// rotate([1, 2, 3, 4, 5, 6], 7) => [6, 1, 2, 3, 4, 5]
@sgzhm4444
Copy link

var arr = [-1, -100, 3, 99];
var k = 5;

for (let i = 0; i < k; i++) {
	let val = arr.pop();
	arr.unshift(val);
}

console.log(arr);

@zxcweb
Copy link

zxcweb commented May 20, 2019

var rotate = function(nums, k) {
    for(var i = 0;i<k;i++){
        nums.unshift(nums.pop())
    }
    return nums;
}

@YouziXR
Copy link

YouziXR commented May 20, 2019

/* 第 77 题:旋转数组算法题

给定一个数组,将数组中的元素向右移动 k 个位置,其中 k 是非负数。

输入: [1, 2, 3, 4, 5, 6, 7] 和 k = 3
输出: [5, 6, 7, 1, 2, 3, 4]
解释:
向右旋转 1 步: [7, 1, 2, 3, 4, 5, 6]
向右旋转 2 步: [6, 7, 1, 2, 3, 4, 5]
向右旋转 3 步: [5, 6, 7, 1, 2, 3, 4] */

const rotateAry = (ary, k) => {
	let len = ary.length
	let rotateNum = k % len
	if (rotateNum === 0) {
		return ary
	}
	let tmpAry = new Array(len)
	ary.forEach((el, index) => {
		if ((index + rotateNum) >= len) {
			tmpAry[index + rotateNum - len] = el
		} else {
			tmpAry[index + rotateNum] = el
		}
	})
	return tmpAry
}
console.log(rotateAry([1, 2, 3, 4, 5, 6, 7], 3))

这么一对比我的写法好low啊= =

@Rashomon511
Copy link

用splice就好了嘛
就不用考虑步数超出数组长度
一行代码解决问题

function rotateArr(arr, k) { 
    return [...arr.splice(k+1), ...arr];
}

image

你这个是不是有点问题,你把key换成1试一试

@francecil
Copy link

francecil commented May 20, 2019

问题转化为:数组的末尾k个元素移动到数组前面
末尾元素:arr.splice(-k%arr.length)的返回值
剩余元素:arr

const moveArr = (arr,k)=>arr.splice(-k%arr.length).concat(arr)

test:
moveArr([1,2,3,4,5,6,7],0) => [1,2,3,4,5,6,7]
moveArr([1,2,3,4,5,6,7],5) => [3,4 5,6,7,1,2]
moveArr([1,2,3,4,5,6,7],8) => [7,1,2,3,4,5,6]

@RichardPear
Copy link

RichardPear commented May 20, 2019

找到一个合适的位置剪掉,unshift到原来的数组, 题目的意思应该是要改变原来的数组,所以直接对原数组开刀。

Array.prototype.rotate = function rotateArr(k = 0) {
    const len = this.length;
    if(!len) {
	return this;
    }
    k = k % len;
    if(k <= 0) {
	return this;
    }
    const cut = this.splice(len - k);
    return this.unshift(...cut);
}
let a = [1, 2, 3, 4, 5, 6];
a.rotate(3);

@ChasLui
Copy link

ChasLui commented May 20, 2019

function rotateArr(arr, k) { 
    return [...arr.splice(k+1), ...arr];
}

拷贝下数组, 防止修改入参

function rotateArr(arr, k) {
  const _tmp = JSON.parse(JSON.stringify(arr));
  return [..._tmp.splice(k + 1), ..._tmp];
}

@benzhemin
Copy link

benzhemin commented May 20, 2019

function rotateStep(arr: any[]) {
  arr.unshift(arr.pop());
}

function rotateTimes(arr: any[], k: number) {
  for(let i=0; i<k; i++) {
    rotateStep(arr);
  }
}

const  arr = [1, 2, 3, 4, 5, 6, 7, 8];
rotateTimes(arr, 1);

console.log(`arr ${JSON.stringify(arr)}`);

@dhzou
Copy link

dhzou commented May 20, 2019

var a = [1,2,3,4,5,6,7];
var move = function(arr,k) {
const len = arr.length
const step = k % len
return arr.slice(len-step).concat(arr.slice(0, len - step))
}
console.log(move(a,3))

@kungithub
Copy link

function f(arr,k){arr.unshift(...arr.splice(-k)); console.log(arr) }

@kingstone3
Copy link

用splice就好了嘛
就不用考虑步数超出数组长度
一行代码解决问题

function rotateArr(arr, k) { 
    return [...arr.splice(k+1), ...arr];
}

image

你这个是不是有点问题,你把key换成1试一试

把 k+1 改成 -k 就好了

@ChasLui
Copy link

ChasLui commented May 20, 2019

function rotate(arr, k) {
  if (!Array.isArray(arr) || !arr.length) {
    console.error('参数 arr 必须为长度大于 0 的数组');
    return [];
  }
  if (!Number.isInteger(k) || k <= 0) {
    console.error('参数 k 必须为非负整数');
    return [];
  }
  const _tmp = JSON.parse(JSON.stringify(arr));
  return [..._tmp.splice(-k % _tmp.length), ..._tmp];
}

// test
const arr = [1, 2, 3, 4, 5, 6, 7];
console.log(rotate(arr, 0)); // [1, 2, 3, 4, 5, 6, 7]
console.log(arr); // [1, 2, 3, 4, 5, 6, 7], 纯函数,不改变原数组
console.log(rotate(arr, 'aaa')); // []
console.log(rotate(arr, 2)); // [ 6, 7, 1, 2, 3, 4, 5 ]

@yaonote
Copy link

yaonote commented May 20, 2019

const changeArr = (arr,k) => {
    const len = arr.length;
    return arr.reduce((acc,curr,idx,origin) => {
        const temp = idx+k <= len-1 ? idx+k : idx+k-len;
        acc[temp] = curr;
        return acc
    },[])
}

@Hunterang
Copy link

let rotArr = (arr,k) => {
let len = arr.length
return [...arr,..arr].slice(k,len+k)
}

@keiseiTi
Copy link

keiseiTi commented May 20, 2019

leetcode 第77题
尽可能想出更多的解决方案,至少有三种不同的方法可以解决这个问题。
要求使用空间复杂度为 O(1) 的原地算法。

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {void} Do not return anything, modify nums in-place instead.
 */
var rotate = function (nums, k) {
  nums.unshift(...nums.splice(nums.length - k, k))
  return nums
};

@wubetter
Copy link

let arr = [1, 2, 3, 4, 5, 6, 7];
let rotate = (arr,k)=>[...arr.slice(-k),...arr.slice(0,-k)]

@bran-nie
Copy link

找到一个合适的位置剪掉,unshift到原来的数组, 题目的意思应该是要改变原来的数组,所以直接对原数组开刀。

Array.prototype.rotate = function rotateArr(k = 0) {
    const len = this.length;
    if(!len) {
	return this;
    }
    k = k % len;
    if(k <= 0) {
	return this;
    }
    const cut = this.splice(len - k);
    return this.unshift(...cut);
}
let a = [1, 2, 3, 4, 5, 6];
a.rotate(3);

这操作。。。
之前了解到的一个建议是尽量避免在原型链上添加方法。

@bran-nie
Copy link

bran-nie commented May 21, 2019

let arr1 = [1, 2, 3, 4, 5]
function func(arr, num) {
    if (num % arr.length === 0) return arr
    return arr.splice(arr.length - (num%arr.length)).concat(arr)
}

image

@pengcc
Copy link

pengcc commented May 21, 2019

let rotateRight = (arr, k) => [...arr.slice(arr.length - k), ...arr.slice(0, arr.length - k)];

@mengsixing
Copy link

function rotateArray(array, step) {
    // 旋转长度超过数组长度,只需要旋转余数就行了
    step = step % array.length;
    // splice 方法同时会将原数组截断
    var rotateArray = array.splice(array.length - step);
    // 重新拼接
    return rotateArray.concat(array);
}
rotateArray([1, 2, 3, 4, 5], 6);

@wingmeng
Copy link

wingmeng commented May 22, 2019

编程式实现,见笑了

function rotateArr(arr, k) {
  let len = arr.length;
  let result = [];

  k = k > len ? k % len : k;

  for (let i = len - 1; i >= 0; i--) {
    if (len - i <= k) {
      result.unshift(arr[i]);
    } else {
      result[i + k] = arr[i];
    }
  }

  return result;
}

@wingmeng
Copy link

因为步数有可能大于数组长度,所以要先取余

function rotate(arr, k) {
  const len = arr.length
  const step = k % len
  return arr.slice(-step).concat(arr.slice(0, len - step))
}
// rotate([1, 2, 3, 4, 5, 6], 7) => [6, 1, 2, 3, 4, 5]

当 k = 0 或 k = arr.length 时,返回结果有误:
rotate([1, 2, 3, 4, 5, 6], 6); // [1, 2, 3, 4, 5, 6, 1, 2, 3, 4, 5, 6]

@i-lijin
Copy link

i-lijin commented May 22, 2019

function rotateArr(arr,k){
return[...arr.splice(-k), ...arr]
}

@LiuMengzhou
Copy link

/**
 * solution1
 * 最短路径逐个转移
 */
var rotate = function (nums, k) {
  const len = nums.length;
  let c = k % len;
  if (c > len / 2) {
    c = len - c;
    while (c > 0) {
      nums.push(nums.shift());
      c--;
    }
  }
  else {
    while (c > 0) {
      nums.unshift(nums.pop());
      c--;
    }
  }
};

/**
 * solution2
 * 妙用API一次性转移
 */
var rotate = function (nums, k) {
  nums.unshift(...nums.splice(- (k % nums.length)));
};

/**
 * solution3
 * 三次翻转
 */
var rotate = function (nums, k) {
  k %= nums.length;
  reverse(nums, 0, nums.length - 1);
  reverse(nums, 0, k - 1);
  reverse(nums, k, nums.length - 1);
};

function reverse(nums, start, end) {
  while (start < end) {
    let temp = nums[start];
    nums[start] = nums[end];
    nums[end] = temp;
    start++;
    end--;
  }
}

@LiuMengzhou
Copy link

LiuMengzhou commented May 23, 2019

用splice就好了嘛
就不用考虑步数超出数组长度
一行代码解决问题

function rotateArr(arr, k) { 
    return [...arr.splice(k+1), ...arr];
}

image

@zpzxgcr 仔细看题目的example老哥

输入: [1, 2, 3, 4, 5, 6, 7]  k = 3
输出: [5, 6, 7, 1, 2, 3, 4]
解释:
向右旋转 1 : [7, 1, 2, 3, 4, 5, 6]
向右旋转 2 : [6, 7, 1, 2, 3, 4, 5]
向右旋转 3 : [5, 6, 7, 1, 2, 3, 4]

@LiuMengzhou
Copy link

var rotate = function(nums, k) {
    for(var i = 0;i<k;i++){
        nums.unshift(nums.pop())
    }
    return nums;
}

@zxcweb k = 10000000000

@LiuMengzhou
Copy link

function rotateArr(arr, k) { 
    return [...arr.splice(k+1), ...arr];
}

拷贝下数组, 防止修改入参

function rotateArr(arr, k) {
  const _tmp = JSON.parse(JSON.stringify(arr));
  return [..._tmp.splice(k + 1), ..._tmp];
}

@ChasLui
这样拷贝数组的操作我头一次见。

const _tmp = [...arr];

@LiuMengzhou
Copy link

LiuMengzhou commented May 23, 2019

function f(arr,k){arr.unshift(...arr.splice(-k)); console.log(arr) }

var rotate = function (nums, k) {
nums.unshift(...nums.splice(nums.length - k, k))
return nums
};

function rotateArr(arr,k){
return[...arr.splice(-k), ...arr]
}

@kungithub
@kingstone3
@yupeilin123
@i-lijin
都试试下面这个case

f([1,2],13);
> [1, 2]

@kingstone3
Copy link

kingstone3 commented May 23, 2019

function f(arr,k){arr.unshift(...arr.splice(-k)); console.log(arr) }
var rotate = function (nums, k) {
nums.unshift(...nums.splice(nums.length - k, k))
return nums
};
function rotateArr(arr,k){
return[...arr.splice(-k), ...arr]
}

@kungithub
@kingstone3
@yupeilin123
@i-lijin
都试试下面这个case

f([1,2],13);
> [1, 2]
function rotateArr(arr, k) { 
  return [...arr.splice(-(k % arr.length)), ...arr];
}

@LiuMengzhou
Copy link

@kingstone3 yes

@jiangmingwen
Copy link

function rotateArr(arr,num){
    return [...arr.slice(arr.length-num),...arr.slice(0,arr.length-num)]
}

rotateArr([1, 2, 3, 4, 5, 6, 7],3)
rotateArr( [-1, -100, 3, 99],2)

@fcater
Copy link

fcater commented Feb 5, 2021

const arr = [1, 2, 3, 4, 5, 6, 7]
const k1 = 3
const arr2 = [-1, -100, 3, 99]
const k2 = 2

function change(arr, k) {
return newArr = [...arr.slice(arr.length - k, arr.length), ...arr.slice(0, arr.length - k)]
}
console.log(change(arr, k1), change(arr2, k2));

@ghost
Copy link

ghost commented Feb 23, 2021

function rotate(arr, step) {
            let len = arr.length;
            let t = step % len;
            let res = new Array(len).fill(null);
            for (let item of arr) {
                res[t%len] = item;
                t++;
            }
            return res;
        }

@hurongju
Copy link

const rotate = (arr, k) => {
  if (arr.length < k) {
    return arr
  }
  for (let i = 0; i < k; i++) { // 旋转k次
    for (let j = arr.length - 1; j > 0; j--) { // 向前冒泡
      [arr[j], arr[j - 1]] = [arr[j - 1], arr[j]]
    }
  }
}

@3104026951
Copy link

let a =[1,2,3,4,5,6,7],k=3;
for(let i=0;i<k;i++) { a.unshift(a.pop())}

@XW666
Copy link

XW666 commented Mar 25, 2021

let arr22 = [1, 2, 3, 4, 5, 6, 7];
 const find02 = (arr, k) => {
   return arr.splice(arr.length - k).concat(arr)
 }

@troubleFisher
Copy link

const rotate = (arr, k) => {
  while (k > 0) {
    arr.unshift(arr.pop());
    k--;
  }
  return arr;
}

const a = [1, 2, 3, 4, 5, 6, 7];
const ret = rotate(a, 8);
console.log(ret) // [7, 1, 2, 3, 4, 5, 6]

@tbapman
Copy link

tbapman commented Apr 25, 2021

// 赞最多的那个写的感觉不够简洁。。

const rotate=(arr,k)=>{
    const slice=arr.splice(arr.length-k)
    return [...slice,...arr]
}

let arr=[1,2,3,4,5,6,7,8]

console.log(rotate(arr,9))

@zhelingwang
Copy link

function rotateArr(arr, offset) {
      for (let i = 0; i < offset; i++) {
        arr.unshift(arr.pop());
      }
      return arr;
    }

    function rotateArr2(arr, offset) {
      return [...arr.slice(arr.length - offset), ...arr.slice(0, arr.length - offset)]
    }

    console.log(rotateArr([1, 2, 3, 4, 5, 6, 7], 3));
    console.log(rotateArr2([1, 2, 3, 4, 5, 6, 7], 4));

@wmb0412
Copy link

wmb0412 commented Jun 9, 2021

	const splitIndex=arr.length-step;
	return arr.slice(splitIndex).concat(arr.slice(0,splitIndex))
}
console.log(rota( [1, 2, 3, 4, 5, 6, 7],3))

@p992202933
Copy link

function rotateArr(arr, k) {
    const arr_len = arr.length
    if(arr_len === 0) return false
    if(arr_len < k) {
        k = k - arr_len
        rotateArr(arr,k)
        return arr
    }
    else{
        let list = []
        list = arr.splice(-k)
        arr.unshift(...list)
        return arr
    }
}

主要就是一个拼接把。。。

@haiyangzhishengs
Copy link

function reversal(arr,k){
while(k>0){
k--
var last = arr.pop()
arr.unshift(last)
}
return arr
}
var arr1 = [1, 2, 3, 4, 5, 6, 7];
console.log(reversal(arr1,4))

@tianfengbiao
Copy link

function re(arr, k) {
var l = arr.length;
var res = []
for(var i = l - 1; i >= 0; i--) {
if(l - k <= i ) {
res.unshift(arr[i]);
} else {
res.splice(k, 0, arr[i])
}

}
console.log('res==',res)
return res

}

@viprespro
Copy link

function rotateArray(arr = [], key = 1) {
  const copy = [...arr]
  const len = arr.length
  const j = key % len
  if(j === 0) return arr
  if (key <= len) {
    for (let i = 0; i < len; i++) {
      if (i + key < len) {
        arr[i + key] = copy[i]
      } else {
        arr[i + key - len] = copy[i]
      }
    }
  }else {
    rotateArray(arr, j)
  }
  return arr
}

来此一游。

@gogopaner
Copy link

function test(arr,count){ return [...arr.slice(arr.length - count),...arr.slice(0,arr.length - count)] }

@ksbaozi
Copy link

ksbaozi commented Sep 25, 2021

const rotate = (arr, = [] step = 0) => arr.splice(-step).concat(arr)

console.log(rotate([1,2,3,4,5,6,7], 4))

// result: [4, 5, 6, 7, 1, 2, 3]

@xiangfei1
Copy link

//nm,我好菜啊,写了这么多,,,
function rotateArr(arr, len) {
  if (len < 0) return '参数不能为负数';
  let newArr = [...arr],
	temp = [];
  while (len > 0) {
	len--;
	for (let i = 0; i < arr.length; i++) {  
	   if (i == arr.length-1) break;
	   temp.push(newArr[i + 1]);
	   newArr[i + 1] = i == 0 ? newArr[i] : temp.shift();
	}
	newArr[0] = temp.pop();
  }
  return newArr;
}

@xiaohan-123
Copy link

使用一个快慢指针,找到需要旋转得部分,然后进行拼接。
function removeK(arr,k) {
let slow = 0,fast = k;
let ans = [];
while(fast < arr.length){
slow++;
fast++;
}
for(let i = slow; i < arr.length; i++){
ans.push(arr[i]);
}
return ans.concat(arr.slice(0,slow));
}
let arr = [1, 2, 3, 4, 5, 6, 7];
console.log(removeK(arr,3));

@sionnigjt
Copy link

function roteArray(arr = [], number) {
    return arr.slice(-number).concat(arr.slice(0, - number))
}
function roteArray2(arr = [], number) {
    return arr.splice(-number).concat(arr)
}
console.log(roteArray([1, 2, 3, 4, 5, 6, 7], 2));
console.log(roteArray2([1, 2, 3, 4, 5, 6, 7], 2));

@yaoocheng
Copy link

有些拉垮了我

let arr = [1, 2, 3, 4, 5, 6, 7], k = 3;
function test1(arr, k) {
    let newArr = [];
    for (let i = 0; i < arr.length; i++) {
        if (k + i < arr.length) {
            newArr[k + i] = arr[i];
        } else {
            newArr[(k + i) - arr.length] = arr[i];
        }
    }
    console.log(newArr)
}
test1(arr, k)

@SnailOwO
Copy link

let k = 3
let ary = [1, 2, 3, 4, 5, 6, 7]

function rightMove(ary,k) {
  const len = ary.length
  if(len) {
    const res = []
     for(let i = 0;i < len;i++) {
      if(i + k > len -1) {
        res[(i + k) % len] = ary[i]
      } else {
        res[i + k] = ary[i]
      }
     }
     return res
  }
}

console.log(rightMove(ary,k));

@Four-Names
Copy link

let arr = [1, 2, 3, 4, 5, 6, 7, 8, 9];
let rotateArr = (arr = Array, k) => [
  ...arr.slice(k % arr.length),
  ...arr.slice(0, k),
];

console.log(rotateArr(arr, 3));

@sexnmaa
Copy link

sexnmaa commented Mar 21, 2022

var rotate = function (nums, k) {
    let m = k % nums.length  
    return nums.splice(0, 0, ...nums.splice(nums.length - m, m))
};

@huimizhang
Copy link

用splice就好了嘛
就不用考虑步数超出数组长度
一行代码解决问题

function rotateArr(arr, k) { 
    return [...arr.splice(k+1), ...arr];
}

image

你这个是不是有点问题,你把key换成1试一试
当k的值超过数组长度的时候就没有用了

@tipsy90s
Copy link

function rotateList(list, k) {
    while(k > 0) {
        let result = list.pop()
        list.unshift(result)
        k--
    }
    return list
}

@xuhen
Copy link

xuhen commented Nov 29, 2022


function rotateArray(arr, k) {
    const len = arr.length;
    const result = [];

    for (let i = 0; i < len; i++) {
        let idx = i + k;
        const newIdx = idx % len;
        result[newIdx] = arr[i];
    }

    return result;
}

@benzhemin
Copy link

const rotateList = (itemList, offset) => {
    const len = itemList.length;
    const realOffset = offset % len;

    return [...itemList.slice(len-realOffset), ...itemList.slice(0, len-realOffset)];
}

const res = rotateList([1, 2, 3, 4, 5, 6, 7], 3);
console.log(res)

const res1 = rotateList([-1, -100, 3, 99], 2);
console.log(res1);

1 similar comment
@benzhemin
Copy link

const rotateList = (itemList, offset) => {
    const len = itemList.length;
    const realOffset = offset % len;

    return [...itemList.slice(len-realOffset), ...itemList.slice(0, len-realOffset)];
}

const res = rotateList([1, 2, 3, 4, 5, 6, 7], 3);
console.log(res)

const res1 = rotateList([-1, -100, 3, 99], 2);
console.log(res1);

@qifengla
Copy link

qifengla commented May 30, 2023

function moveArr(arr, k) {
	for (let i=0; i<k; i++) {
		let tmp = arr.pop();
		arr.unshift(tmp)
	}
	return arr
}

let arr1 = [1,2,3,4,5,6,7], k = 3;
arr1 = moveArr(arr1, k);
console.log(arr1)

@88wixi
Copy link

88wixi commented Jul 21, 2023

/* 第 77 题:旋转数组算法题
给定一个数组,将数组中的元素向右移动 k 个位置,其中 k 是非负数。
输入: [1, 2, 3, 4, 5, 6, 7] 和 k = 3
输出: [5, 6, 7, 1, 2, 3, 4]
解释:
向右旋转 1 步: [7, 1, 2, 3, 4, 5, 6]
向右旋转 2 步: [6, 7, 1, 2, 3, 4, 5]
向右旋转 3 步: [5, 6, 7, 1, 2, 3, 4] */
let arr = [1, 2, 3, 4, 5, 6, 7]
let k = 3
let changearr = [...arr]
function rotateArr(arr, k) {
for (index in arr) {
console.log(typeof index)
if (Number(index) < arr.length - k) {
changearr[Number(index) + k] = arr[Number(index)]
} else {
let reindex = (Number(index) + k) % arr.length
changearr[reindex] = arr[Number(index)]
}
}
}
rotateArr(arr,k)
console.log(changearr)

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