如何在不获取 O(n)^3 的情况下遍历包含 2D 数组的对象？

Question

希望这不是一个太具体的问题，但我希望深入了解如何使用嵌套对象和数组，而无需制作运行 O(n)^2 或 O(n)^ 的程序3.

下面是我编写的一个程序，用于查找从 A 点到 B 点的最便宜航班，如果航班价格相同，则查找航班数量最少的航班。您会看到我在哪里标记了效率不高的部分。我怎样才能使这些更有效率？

//returns an object with an array of IDs that will get you to a destination at the lowest cost. if same cost, then the least amount of flights flights

function leastExpensiveFlight(flightInfo, start, end) {
  var numOfTimes = 1
  var combinedValues = []
  var minValue
  var indexOfMinValue;
  var numOfFlights = []
  var minNumberOfFlights;
  var startTimes = flightInfo.reduce((startTimes, f, index) => {
    if (f[0] == start) {
      startTimes[numOfTimes] = [f];
      numOfTimes++
    }
    return startTimes
  }, {})
  //below is O(n)^2  
  //Gets the Flights where Location 1 = start 
  for (i = 0; i < Object.keys(startTimes).length; i++) {
    for (j = 0; j < startTimes[Object.keys(startTimes)[i]].length; j++) {
      flightInfo.forEach((f, ) => {
        if (startTimes[Object.keys(startTimes)[i]][j] &&
          f[0] === startTimes[Object.keys(startTimes)[i]][j][1] &&
          startTimes[Object.keys(startTimes)[i]][j][1] <= end &&
          f[1] <= end) {
          if (!startTimes[Object.keys(startTimes)[i]].includes(f)) {
            startTimes[Object.keys(startTimes)[i]].push(f)
          }
        }
      })
    }
  }
  //below is O(n)^3!!
  //Finds trips that will get to the destination
  Object.keys(startTimes).forEach((flights) => {
    startTimes[flights].forEach((subFlights1, sFIndex1) => {
      startTimes[flights].forEach((subFlights2, sFIndex2) => {
        if (subFlights1[0] === subFlights2[0] &&
          subFlights1[1] === subFlights2[1] &&
          sFIndex1 != sFIndex2) {
          if (subFlights1[2] >= subFlights2[2]) {
            startTimes[flights].splice(sFIndex1, 1)
          } else {
            startTimes[flights].splice(sFIndex2, 1)
          }
        }
      })
    })
  })
  //below is O(n)^2  
  //Finds the trip with the minimum value and, if same price, least amount of flights
  Object.keys(startTimes).forEach((flights, sTIndex) => {
    startTimes[flights].forEach((subFlights, sFIndex) => {
      if (sFIndex == 0) {
        combinedValues[sTIndex] = subFlights[2]
        numOfFlights.push(1)
      } else {
        combinedValues[sTIndex] += subFlights[2]
        numOfFlights[sTIndex] += 1
      }
      if (sFIndex === startTimes[flights].length - 1 &&
        ((combinedValues[sTIndex] <= minValue) ||
          !minValue)) {
        if ((!minNumberOfFlights ||
            minNumberOfFlights > numOfFlights[sTIndex])) {
          minNumberOfFlights = numOfFlights[sTIndex]
        }
        if (combinedValues[sTIndex] === minValue &&
          numOfFlights[sTIndex] === minNumberOfFlights ||
          (combinedValues[sTIndex] < minValue &&
            numOfFlights[sTIndex] >= minNumberOfFlights) ||
          !minValue) {
          minValue = combinedValues[sTIndex];
          indexOfMinValue = sTIndex
        }
      }
    })
  })

  return startTimes[Object.keys(startTimes)[indexOfMinValue]]
} //Big O is O(n)^3

//2D Array: data[0][0] = Location start,
//          data[0][1] = Location end,
//          data[0][2] = Price,
//          
var data = [
  [4, 5, 400],
  [1, 2, 500],
  [2, 3, 300],
  [1, 3, 900],
  [2, 3, 100],
  [3, 4, 400]
]

//so from location 1 - location 3, the cheapest route would be: [1,2,500],[2,3,100]
console.log(JSON.stringify(leastExpensiveFlight(data, 1, 3)));

非常感谢您的帮助。我正在努力提高编码水平，以便进入我的工程部门，但如您所见，我还有很长的路要走。

[编辑]- 抱歉，我刚刚修正了其中的错误陈述。

Answer 1

我会首先为开始节点和结束节点之间的每条可能路径构造一个 graph 来解决这个问题。创建一个函数，给定起始节点和已访问的节点列表，可以查看数据以找到引出该节点的每条路径。对于每条 尚未访问 的路径，如果路径在目的地结束，则将行进路径的全部结果推送到 finishedPaths 数组。否则，递归调用该函数，使其再次执行相同的过程，从结束节点开始。

为了降低复杂性，为了确定一个节点是否已经被访问过，使用一个对象或集合（它们在 O(1) 时间内进行查找，不像 Array.prototype.includes，它在 Array.prototype.includes 中运行O(n)次）。

最后，遍历起点和终点之间的所有可能路径，找出成本最低的路径，并在其中找到路径数量最少的路径。

function leastExpensiveFlight(data, start, end) {
  const pathsByStartLoc = {};
  for (const path of data) {
    const start = path[0];
    if (!pathsByStartLoc[start]) pathsByStartLoc[start] = [];
    pathsByStartLoc[start].push(path);
  }
  const getAllPaths = (
    start,
    costSoFar = 0,
    pathsSoFar = [],
    finishedPaths = [],
    visitedNodes = {}
  ) => {
    if (!pathsByStartLoc[start]) return;
    for (const path of pathsByStartLoc[start]) {
      if (visitedNodes.hasOwnProperty(path[2])) continue;
      if (path[1] === end) {
        finishedPaths.push({ totalCost: costSoFar + path[2], paths: [...pathsSoFar, path] });
      }
      getAllPaths(
        path[1],
        costSoFar + path[2],
        [...pathsSoFar, path],
        finishedPaths, { ...visitedNodes, [path[0]]: true }
      );
    }
    return finishedPaths;
  };
  const allPaths = getAllPaths(start);
  const lowestCost = Math.min(...allPaths.map(({ totalCost }) => totalCost));
  const lowestCostPaths = allPaths.filter(({ totalCost }) => totalCost === lowestCost);
  return lowestCostPaths.reduce((a, item) => a.paths.length < item.paths.length ? a : item);
}       
var data = [
  [4, 5, 400],
  [1, 2, 500],
  [2, 3, 300],
  [1, 3, 900],
  [2, 3, 100],
  [3, 4, 400]
]

//so from location 1 - location 3, the cheapest route would be: [1,2,500],[2,3,300]
console.log(leastExpensiveFlight(data, 1, 3));

如何在不获取 O(n)^3 的情况下遍历包含 2D 数组的对象？

How do I iterate through an object containing 2D arrays without getting O(n)^3?

javascript

big-o

object

nested-loops

multidimensional-array