javascript - 查找数组中最接近的匹配对

Question

我试图在 n 时间内用算法找出数组中最接近的匹配对。

我在下面的 repl 中创建了一个解决方案，但我不确定它是什么大 O。我猜可能是 (Onlogn) 或 O(logn)。如果可能的话，我想把它缩短到 O(n) 时间。

let closestMatchingPair = function(array) {
  if(!array || array.length < 2) {
		return 'invalid data get bent';
	}
	let pairFound = false;
	let position1 = 0;
	let position2 = 0;
	let distance = array.length;

	object = {};
	//build object 
	for(let i = 0; i < array.length; i++) {
		if(!object[array[i]]) {
			object[array[i]] = [i];
		} else {
			object[array[i]].push(i);
		}
	}
  //loop over object properties
	for(let i = 0; i < array.length-1; i++) {
		if(object[array[i]].length >= 2) {
			var closest = object[array[i]].filter(a => a > i).shift();
			if(distance > (closest - i)) {
				position1 = i;
				position2 = closest;
				distance = closest - i;
				pairFound = true;
			}
		}
	}

	return {
		pairFound: pairFound,
		position1: position1,
		position2: position2,
		distance: distance
	}
}

//example [1] = 'invalid data get bent'
//example [1,2] = { pairFound: false, position1: 0, position2: 0, distance: 2 }
//example [1,2,1] = { pairFound: true, position1: 0, position2: 2, distance: 2 }
//example [1,2,1,3,2,2] = { pairFound: true, position1: 4, position2: 5, distance: 1 }
let array = [1,2,1,3,2,2];

console.log(closestMatchingPair(array));

https://repl.it/@zack_fanning/PushyGoodnaturedOutput

按预期工作，希望尽可能避免在第 22 行使用过滤器

var closest = object[array[i]].filter(a => a > i).shift();

Answer 1

您正在做很多不必要的工作。像您一样预先构建一个对象通常是个好主意，但在这种情况下这不是胜利。您只需要遍历数组一次，并且在迭代之间只需要跟踪几个事实:

• prevPositions – 一个对象，用于跟踪到目前为止看到的每个项目的最新索引。
• distance – 迄今为止任何对之间的最小距离。
• position1 , position2 – 迄今为止距离最小的对的索引。

(从技术上讲，distance 总是可以通过从 position1 中减去 position2 来计算，但我们将通过单独存储它来节省一些工作。)

在每次迭代中，您需要:

1. 检查您之前是否看过当前项目。
   • 如果是，检查当前项与其上一次出现之间的距离是否小于目前为止的最小距离。
     • 如果是，将新的最小距离存储在distance中以及 position1 中当前和先前事件的索引和 position2 .
2. 将当前项目的索引存储在prevPositions 中.

在您对每个项目进行一次迭代之后，position1 , position2 , 和 distance将包含最近对的索引和它们之间的距离。

这是O(n)。您可以在下面的代码片段中看到它在 JavaScript 中的样子。

function closestMatchingPair(array) {
  if (array.length < 2) {
    throw new Error('Input must have at least two items');
  }
  
  // An object to track the most recent positions of the items we've seen so far
  const prevPositions = {};

  // Variables to track the smallest distance so far and corresponding indexes
  let distance, position1, position2;

  for (let index = 0; index < array.length; index++) {
    const currentItem = array[index];

    if (currentItem in prevPositions) {
      // We've seen this item before; check if the distance from the previous 
      // instance is less than the smallest distance we've seen so far
      const currentDistance = index - prevPositions[currentItem];

      if (!distance || currentDistance < distance) {
        // New smallest distance; update our variables
        distance = currentDistance;
        position1 = prevPositions[currentItem];
        position2 = index;
        
        if (currentDistance === 1) {
          // Can't do any better than 1; no reason to continue
          break;
        }
      }
    }
    prevPositions[currentItem] = index; // Save item's index
  }

  return { pairFound: !!distance, position1, position2, distance };
}

test([1]);
test([1,2]);
test([1,2,1]);
test([1,2,1,3,2,2]);

function test(input) {
  console.log('input:', input);
  try {
    console.log('output:', closestMatchingPair(input));
  } catch (e) {
    console.error(e.message);
  }
}

.as-console-wrapper{min-height:100%}

注意:此代码使用一个普通对象表示 prevPositions .只要您的输入数组仅包含数字或仅包含字符串，它就可以正常工作。但是，如果您的输入是[1, '1']这两个值将被视为相等，因为数字键在用作对象属性名称时被强制转换为字符串。 (从技术上讲，它比这复杂一点，但你明白了。)如果你想让它与混合数组一起工作，你需要使用 Map。而不是对象。