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

第 161 题:用最精炼的代码实现数组非零非负最小值index #421

Open
libin1991 opened this issue Sep 15, 2020 · 185 comments
Open

Comments

@libin1991
Copy link

libin1991 commented Sep 15, 2020

例如:[10,21,0,-7,35,7,9,23,18] 输出5, 7最小

function getIndex(arr){
      let index=null;
      ...
      return index;
}
@libin1991 libin1991 changed the title 用最精炼的代码实现数组非零最小值index 第 161 题:用最精炼的代码实现数组非零最小值index Sep 15, 2020
@slogeor
Copy link

slogeor commented Sep 16, 2020

/**
 * @description 用最精炼的代码实现数组非零最小值 index
 * @param {array} arr 数组
 * @returns {number} index 索引
 */
function getIndex(arr) {
      let index = -1;
      const minVal = arr.reduce((cur, pre) => {
            return (cur <= 0 || pre <= 0) ? Math.max(cur, pre) : cur > pre ? pre : cur;
      }, -1);
      index = arr.findIndex(item => item == minVal && minVal > 0)
      return index;
}

@libin1991
Copy link
Author

@slogeor reduce和reduce一起复杂度是多少? 没有体现最精炼

@libin1991 libin1991 changed the title 第 161 题:用最精炼的代码实现数组非零最小值index 第 161 题:用最精炼的代码实现数组非零非负最小值index Sep 16, 2020
@slogeor
Copy link

slogeor commented Sep 16, 2020

@libin1991 上面的时间复杂度是 O(N^2),

function getIndex(arr) {
      let index = -1;
      arr.reduce((pre, cur, k) => {
            if (cur <= 0 || pre <= 0) {
                  index = cur <= 0 && pre <= 0 ? -1 : cur > pre ? k : index;
            } else {
                  index = cur > pre ? index : k;
            }
            return cur > pre ? pre : cur;
      }, -1);
      return index;
}

时间复杂度是 O(N)

@tanxin03
Copy link

import postwroker from 'worker-loader!./postworker'
有人知道加!这种引入方法是什么意思吗

@slogeor
Copy link

slogeor commented Sep 16, 2020

@tanxin520 上下文方便说一下嘛

@tanxin03
Copy link

https://www.webpackjs.com/loaders/worker-loader/
您访问下这个地址,这上面有这个demo,但是没讲这个!的意思,我想了解一下,麻烦了 @slogeor

@slogeor
Copy link

slogeor commented Sep 21, 2020

const arr = [10, 21, 0, -7, 35, 7, 9, 23, 18];

function findMinimumIndex(arr) {
  return arr.findIndex(item => item === arr.filter(item => item > 0).sort((a, b) => a - b)[0])
}
console.log(findMinimumIndex(arr))

这个时间复杂度也不低

@slogeor
Copy link

slogeor commented Sep 22, 2020

@libin1991 楼主,我是否可以贡献一题,实现 JSON.stringify 方法

@libin1991
Copy link
Author

libin1991 commented Sep 22, 2020

@libin1991 上面的时间复杂度是 O(N^2),

function getIndex(arr) {
      let index = -1;
      arr.reduce((pre, cur, k) => {
            if (cur <= 0 || pre <= 0) {
                  index = cur <= 0 && pre <= 0 ? -1 : cur > pre ? k : index;
            } else {
                  index = cur > pre ? index : k;
            }
            return cur > pre ? pre : cur;
      }, -1);
      return index;
}

时间复杂度是 O(N)

function getIndex(arr) {
      let index = -1;
      arr.reduce((pre, cur, k) => {
            if (cur <= 0 || pre <= 0) {
                  index = cur <= 0 && pre <= 0 ? -1 : cur > pre ? k : index;
            } else {
                  index = cur > pre ? index : k;
            }
            return cur > pre ? pre : cur;
      }, -1);
      return index;
}

输出答案都是错的!

getIndex([10,21,0,-7,35,7,9,23,18])
// 8

@slogeor
Copy link

slogeor commented Sep 22, 2020

@libin1991 上面的时间复杂度是 O(N^2),

function getIndex(arr) {
      let index = -1;
      arr.reduce((pre, cur, k) => {
            if (cur <= 0 || pre <= 0) {
                  index = cur <= 0 && pre <= 0 ? -1 : cur > pre ? k : index;
            } else {
                  index = cur > pre ? index : k;
            }
            return cur > pre ? pre : cur;
      }, -1);
      return index;
}

时间复杂度是 O(N)

function getIndex(arr) {
      let index = -1;
      arr.reduce((pre, cur, k) => {
            if (cur <= 0 || pre <= 0) {
                  index = cur <= 0 && pre <= 0 ? -1 : cur > pre ? k : index;
            } else {
                  index = cur > pre ? index : k;
            }
            return cur > pre ? pre : cur;
      }, -1);
      return index;
}

输出答案都是错的!

getIndex([10,21,0,-7,35,7,9,23,18])
// 8

调整了一下

function getIndex(arr) {
    if (!arr.length) return -1;
    let index = -1;
    arr.reduce((pre, next, k) => {
        const min = Math.min(pre, next);
        const max = Math.max(pre, next, 0);
        // 都是正数
        if (pre > 0 && next > 0) {
            index = min === pre ? index : k
            return min;
        }

        index = (max === 0 ||  max === pre) ? index : k;
        return max;
    }, 0)
    return index;
}

@slogeor
Copy link

slogeor commented Sep 22, 2020

常规写法

function rankVoteMaxIndex(arr) {
            let itemIndex = 0;   // 非0最小index
            let itemRank=0;      // 非0最小值
            let length=arr.length;
            if(!length){
                 return -1;
            }
            for(let i=0;i<length;i++){
                let item=arr[i];
                if(item<0) continue;
                if(!itemRank) {
                    itemIndex = i;
                    itemRank = item;
                }
                if(item < itemRank ){
                    itemIndex = i;
                    itemRank = item;
                }
               
            }
            return itemIndex;
        }

这个答案面试官给了65分(满分100)

rankVoteMaxIndex([-1] // 0
rankVoteMaxIndex([-1, 0, 1] // 0

@libin1991
Copy link
Author

image

<script>

    function rankVoteMaxIndex(arr) {
        let itemIndex = -1;   // 非0最小index
        let itemRank = -1;      // 非0最小值
        let length = arr.length;
        if (!length) {
            return itemIndex;
        }
        for (let i = 0; i < length; i++) {
            let item = arr[i];
            if (item > 0) {
                if (itemRank < 0) {
                    itemIndex = i;
                    itemRank = item;
                }
                if (item < itemRank) {
                    itemIndex = i;
                    itemRank = item;
                }
            }

        }
        return itemIndex < 0 ? -1 : itemIndex;
    }

    // rankVoteMaxIndex([-1] // 0
    // rankVoteMaxIndex([-1, 0, 1] // 0

    console.log(rankVoteMaxIndex([-1]));
    console.log(rankVoteMaxIndex([-1, 0, 1]));
    console.log(rankVoteMaxIndex([10, 21, 0, -7, 35, 7, 9, 23, 18]))
    console.log(rankVoteMaxIndex([0, 10, 21, 0, -7, 35, 7, 9, 23, 18]))
</script>

@XuedaoYuan
Copy link

会不会B格不够高

const arr = [-10, 0, 10, 21, 0, -7, 35, 7, 9, 23, 18]
let minNum
let minIndex = -1
for (let i = 0, len = arr.length; i < len; i++) {
	if (minNum) {
		if (arr[i] < minNum && arr[i] > 0) {
			minNum = arr[i]
			minIndex = i
		}
	} else {
		if (arr[i] > 0) {
			minNum = arr[i]
			minIndex = i
		}
	}
}

console.log(minIndex, minNum)

@HuiGeGeGitHub
Copy link

HuiGeGeGitHub commented Sep 25, 2020

const minIndex = (arr) => arr.reduce((num, v, i) => v > 0 && v < arr[num] ? i : num, 0)

@MissNanLan
Copy link

先找出大于0的数,然后排序,最小值就是非负非零的最小值,楼上的这个也算一个方法

@llllllllr
Copy link

llllllllr commented Oct 16, 2020

const minIndex = (arr) => arr.reduce((num, v, i) => v > 0 && v < arr[num] ? i : num, -1)

初始值为-1的话是没法找到最小值的,经测试这条式子有点问题,做了一点调整,代码如下

// 先找到第一个非负非零的值的下标
function findInitialValue(arr) {
  for (let i = 0; i < arr.length; i++) {
    if (arr[i] > 0) return i;
  }
  return -1;
}
const arr = [10, 21, 0, -7, 35, 7, 9, 23, 18];
function minIndex(arr) {
  let first = findInitialValue(arr);
  // 无非负非零的数,直接返回-1
  if (first === -1) return -1;
  return arr.reduce(
    (num, cur, curIndex) => (cur > 0 && cur < arr[num] ? curIndex : num),
    // 关键是reduce的初始值
    first
  );
}
console.log(minIndex(arr)); // 5

reduce用法相关参考链接:
https://aotu.io/notes/2016/04/14/js-reduce/index.html

@xueshuai
Copy link

xueshuai commented Oct 16, 2020

function getIndex(arr) {
	return arr.reduce((idx, cur, k) => idx = cur <= idx[1] && cur > 0 ? [k, cur] : idx, [-1, Number.MAX_SAFE_INTEGER])[0]
}

@zhanhongtao
Copy link

const minIndex = (arr) => arr.reduce((num, v, i) => v > 0 && v < arr[num] ? i : num, -1)

初始值为-1的话是没法找到最小值的,经测试这条式子有点问题,做了一点调整,代码如下

// 先找到第一个非负非零的值的下标
function findInitialValue(arr) {
  for (let i = 0; i < arr.length; i++) {
    if (arr[i] > 0) return i;
  }
  return -1;
}
const arr = [10, 21, 0, -7, 35, 7, 9, 23, 18];
function minIndex(arr) {
  let first = findInitialValue(arr);
  // 无非负非零的数,直接返回-1
  if (first === -1) return -1;
  return arr.reduce(
    (num, cur, curIndex) => (cur > 0 && cur < arr[num] ? curIndex : num),
    // 关键是reduce的初始值
    first
  );
}
console.log(minIndex(arr)); // 5

reduce用法相关参考链接:
https://aotu.io/notes/2016/04/14/js-reduce/index.html

code:

arr.reduce((res, value, index) => value > 0 && (res === -1 || arr[index] < arr[res]) ? index : res, -1)

@Mrcxt
Copy link

Mrcxt commented Oct 27, 2020

实现的比较low,用for对比实现的:

(() => {
    function getIndex(arr) {
        let index;
        let n = Infinity;
        for (let i = 0; i < arr.length; i++) {
            const item = arr[i];
            if (item > 0 && item<n) {
                n = item;
                index = i;
            }
        }

        return index;
    }

    let arr = [10, 21, 0, -7, 35, 7, 9, 23, 18]

    console.log(getIndex(arr));
})();

@littleebirds
Copy link

function getIndex(arr){
  let index = null
  index = arr.reduce((temp, v, i, arr)=>{
    if(v > 0 && v < arr[temp]){
      return i
    }else{
      return temp
    }
  }, 0)
  return index
}

@shetia
Copy link

shetia commented Nov 9, 2020

// 不知道有没有重复的元素, 那就直接取了最前出现的, 时间复杂度O(n), 空间复杂度O(1)
function getIndex(arr){
  let index = -1;
  let min = Infinity
  for(let i = 0; i < arr.length; i++){
    if(arr[i] > 0 && arr[i] < min) {
      min = arr[i]
      index = i
    }
  }
  return index;
}

let test = [
  [[10,21,0,-7,35,7,9,23,18], 5],
  [[10,21,0,-7,35,7,9,23,1], 8],
  [[1,21,0,-7,35,7,9,23,1], 0],
  [[], -1]
]
for(let i = 0; i < test.length; i++){
  let [arr, n] = test[i]
  console.log(getIndex(arr) === n)
}

其实就看怎么理解最精简, 我认为是时间空间复杂度小的,
如果说从代码行数来讲, 并没有什么意义, 都可以压缩成一行代码,
还有就是有可读性

@DarthVaderrr
Copy link

function getIndex(arr){
  const indexMap = arr.reduce((map,item,index) => { map[item] = index ; return map;}, {});
  return indexMap[arr.filter(i => i>0).sort(a, b => a - b)[0]] || -1;
}

@hcc0007
Copy link

hcc0007 commented Nov 12, 2020

function getIndex(arr) {
  const min = Math.min(...(arr.filter(i => i > 0)));
  const index = arr.indexOf(min);
  return index + ',' + min;
}

const arr = [10,21,0,-7,35,7,9,23,18];
console.log(getIndex(arr));

@asiyk-ava
Copy link

asiyk-ava commented Nov 13, 2020

最精炼的代码,没说是最小的复杂度啊

function getIndex(arr) {
        let min=Math.min(...arr.filter(i=>i>0));
        let index=arr.indexOf(min);
        return [index, min].join(', ');
}

@brushbird
Copy link

最精炼的代码,没说是最小的复杂度啊

function getIndex(arr) {
        let min=Math.min(...arr.filter(i=>i>0));
        let index=arr.indexOf(min);
        return [index, min].join(', ');
}

赞同👍

@JiangMengLei
Copy link

const minIndex = (arr) => arr.reduce((num, v, i) => v > 0 && v < arr[num] ? i : num,0)

@zhouhan1033
Copy link

zhouhan1033 commented Nov 18, 2020

// 方法一
function getIndex(arr){
    let index = null;
    let min;
    for(let i = 0, l = arr.length; i < l; i++) {
        if(arr[i] < min && arr[i] > 0 || !min && arr[i] > 0) {
            min = arr[i];
            index = i;
        }
    }
    return index;
}

//方法二
function getIndex(arr){
    return arr.indexOf(Math.min(...arr.filter(v => v > 0)));
}

@ReAlign
Copy link

ReAlign commented Nov 18, 2020

function getIndex(arr) {
    return arr.reduce((v, x, i, ori) => x > 0 ? (x < ori[(v === -1 ? 0 : v)] ? i : v) : v, -1);
}

@Lemon-Cai
Copy link

Lemon-Cai commented Aug 18, 2022 via email

@Anber-H
Copy link

Anber-H commented Sep 22, 2022

function findMin(arr){
return arr.findIndex(v=>v===Math.min.apply(null,arr.filter(v=>v>0)))
}

@Lemon-Cai
Copy link

Lemon-Cai commented Oct 9, 2022 via email

@271853754
Copy link

271853754 commented Oct 9, 2022

首末尾递归

const getIndex = (arr, l=0, r = arr.length-1) =>
   (l>=r)?l:(arr[l]>0 && (arr[r]<=0 || arr[l]<arr[r]))?getIndex(arr, l, r-1):getIndex(arr, l+1, r)

getIndex([10,21,0,-7,35,7,9,23,18])

非递归(用于理解上面的递归)

const list = [10,21,0,-7,35,7,9,23,18];
let index = -1;
let value = Number.MAX_SAFE_INTEGER;

let leftIndex = 0;
let rightIndex = list.length - 1;
while(leftIndex <= rightIndex) {
  const leftValue = list[leftIndex];
  if(leftValue<=0) {
    leftIndex++;
    continue;
  }
  const rightValue = list[rightIndex];
  if(rightValue<=0) {
    rightIndex--;
    continue;
  }
  if(leftValue<rightValue) {
    rightIndex--;
  } else {
    leftIndex++;
  }
}
console.log(leftIndex);

@DouJiangGet
Copy link

function getIndex (arr) {
let minnum = arr[0], minindex;
for (let index = 0; index < arr.length; index++) {
if (arr[index] > 0 && arr[index] <= minnum) {
minnum = arr[index]
minindex = index;
}
}
return minindex;
}

console.log(getIndex([10, 21, 0, -7, 35, 7, 9, 23, 18])); 

@SlahserZ
Copy link

function getSmallestPositiveInteger(nums) {
    let ret = []; // tuple of 2D.
    for (let i = 0; i < nums.length; i++) {
        if((!ret[0] && !ret[1]) || (nums[i] < ret[0] && nums[i] > 0)) {
            ret = [nums[i], i]; 
        }
    }
   return ret;
}

@FE-runner
Copy link

FE-runner commented Nov 15, 2022

const findMin = (arr)=>{
  return arr.reduce((total,value,index)=>{
    if(value>0&&value<arr[total!==undefined?index:0]){
      return index
    }else{
      return total
    }
  },undefined)
}

@greatInvoker
Copy link

greatInvoker commented Jan 6, 2023

image
image

@ElderlyBoy
Copy link

ElderlyBoy commented Feb 3, 2023

function getIndex(arr) {
  let index = arr.findIndex(item => item === Math.min(...(arr.filter(n => n > 0))))
  return `${index},${arr[index]}`
}

getIndex([10, 21, 0, -7, 35, 7, 9, 23, 18])
//'5,7'

image

@ruanzhijian
Copy link

function getIndex(arr) {
let ansIndex = 0;
arr.reduce((acc, cur, index) => {
if (cur > 0 && cur < acc) {
acc = cur;
ansIndex = index;
}
return acc;
}, +Infinity);
return ansIndex;
}

@forgivenoom
Copy link

每次记录最小数角标, 数字小于0跳过, 否则与上次角标的数字比较,返回较小的角标

const getMinIndex = (e) => {
return e.reduce((p, c, i, ary) => {
if (c < 0) return p
return c < ary[p] ? i : p
}, 0)
}

@xiaoguoaa
Copy link

function getIndex(arr) {
  let index = 0;
  for (let i = 0; i < arr.length; i++) {
    if (arr[i] > 0 && arr[i] < arr[index]) {
      index = i;
    }
  }
  return index;
}

@2113ic
Copy link

2113ic commented Apr 19, 2023

我补充一个蠢方法🤡

// 获取大于0的值的索引
function getIndex(arr) {
  let index, temp = Infinity;

  arr.forEach((item, i) => {
    if (item > 0 && item < temp) {
      index = i;
      temp = item;
    }
  });

  return index;
}

@adoin
Copy link

adoin commented May 27, 2023

function getIndex(arr){

return arr.indexOf(Math.min(...arr.map(m=>m>0?m:Infinity)))
    
}

@PhoenixMenia
Copy link

function getIndex(arr){ let index = 0; arr.forEach((item, _index) => { if(arr[index] <= 0 || (item > 0 && item < arr[index])) { index = _index; } }) return index; }

@ZegTsai
Copy link

ZegTsai commented Aug 29, 2023

function getIndex(arr) {
  let index = null;
  for (let i = 0, len = arr.length, min = Infinity; i < len; i++) {
    const item = arr[i];
    item > 0 && item < min && ([min, index] = [item, i]);
  }
  return index;
}

console.log(getIndex([-1, -2]));
console.log(getIndex([0, 0]));
console.log(getIndex([-1, 0, 1]));
console.log(getIndex([10, 21, 0, -7, 35, 7, 9, 23, 18]));
console.log(getIndex([0, 10, 21, 0, -7, 35, 7, 9, 23, 18]));
console.log(getIndex([6, 4, 1, 2, 3, 4, 5]));

@PhoenixMenia
Copy link

PhoenixMenia commented Aug 29, 2023 via email

@wendyquan0801
Copy link

function findMinIndex(arr) {
return arr.reduce(
(minIdx, curr, index) => (curr > 0 && (arr[minIdx] <= 0 || curr < arr[minIdx]) ? index: minIdx),
0
);
}

@guoguo469
Copy link

function getIndex(arr){
  let index=null
  let min = Infinity
  for(let i = 0; i < arr.length - 1 ; i++) {
    if(arr[i] < min && arr[i] > 0) {
      min = arr[i]
      index = i
    }
  }
  return index;
}

@Jisl
Copy link

Jisl commented Oct 12, 2023

// 用最精炼的代码实现数组非零非负最小值 index
// 例如:[10,21,0,-7,35,7,9,23,18] 输出 5, 7 最小
function getIndex(arr) {
  let index = null;
  let min = 0;
  arr.forEach((item, i) => {
    if (item <= 0) return;
    if (!index || item < min) {
      index = i;
      min = item;
    }
  });
  return index;
}
console.log(getIndex([10, 21, 0, -7, 35, 7, 9, 23, 18]));

function getIndexByReduce(arr) {
  return arr.reduce(
    (res, item, index) =>
      item > 0 && (item < arr[res || 0] || res === null) ? index : res,
    null
  );
}
console.log(getIndexByReduce([10, 21, 0, -7, 35, 7, 9, 23, 18]));

@zxcc-cx
Copy link

zxcc-cx commented Oct 25, 2023

function getIndex(arr) { let index = null; arr.reduce((...args)=>{ console.log(args,index); if(index == null){ index = args[1]>0?args[2]:null; }else{ index = (args[1]>0&&args[1]<arr[index])?args[2]:index; } return args[1]; },0) return index; } console.log(getIndex([10, 21, 0, -7, 35, 7, 9, 23, 18]));

@zhenmingDev
Copy link

export function getIndex(arr) {
let index = null;
let accList = arr.reduce((acc, cur, index) => {
return (cur > 0 && cur < acc[0]) ? [cur, index] : acc
}, [arr[0], 0])
index = accList[1]
return index;
}

@PhoenixMenia
Copy link

PhoenixMenia commented Nov 20, 2023 via email

@NAZBIN
Copy link

NAZBIN commented Nov 20, 2023

const getMinIndex = (arr) => {
let minIndex = 0;

const isMinValue = (item) => {
return item > 0 && item < arr[minIndex];
};

arr.map((item, idx) => {
minIndex = isMinValue(item) ? idx : minIndex;
});

return [minIndex, arr[minIndex]];
};

@NAZBIN
Copy link

NAZBIN commented Nov 20, 2023

const getMinIndex = (arr) => { let minIndex = 0;

const isMinValue = (item) => { return item > 0 && item < arr[minIndex]; };

arr.map((item, idx) => { minIndex = isMinValue(item) ? idx : minIndex; });

return [minIndex, arr[minIndex]]; };

map改为foreach

@ruanshr
Copy link

ruanshr commented Jan 24, 2024

function getMinIndex(arr) {
return arr.reduce(([n, i], m, idx) => m < n && m > 0 ? [m, idx] : [ n, i ], [Number.MAX_VALUE],-1).at(-1)
}

@PhoenixMenia
Copy link

PhoenixMenia commented Jan 24, 2024 via email

@zlh-GitHub
Copy link

const minIndex = (arr) => arr.reduce((num, v, i) => v > 0 && v < arr[num] ? i : num, 0)

const minIndex = (arr) => arr.reduce((num, v, i) => v > 0 && v < (arr[num] || Infinity) ? i : num, -1) 默认索引-1,再判断下arr[num]的值比较对

@PhoenixMenia
Copy link

PhoenixMenia commented May 7, 2024 via email

@chens01
Copy link

chens01 commented May 20, 2024

排序 + indexOf
function getIndex(arr){
let arr2 = arr.toSorted((a,b) => a - b);
return arr.indexOf(arr2.find(v => v > 0));
}

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

No branches or pull requests