查找陣列中的連續匹配位置

我有一組位置並希望找到與第一個位置不同的第一個位置（或一組位置）。「不同」是指基於確定它們距離的函數的明顯不同的位置。下面是一個示例數組：查找陣列中的連續匹配位置

[ 
    {lat: 45, lng: 45},   // 1st Location 
    {lat: 45.01, lng: 45.01},  // 1st Location 
    {lat: 55, lng: 55},   // 2nd Location - MATCH 
    {lat: 55.01, lng: 55.01},  // 2nd Location - MATCH 
    {lat: 54.99, lng: 54.99},  // 2nd Location - MATCH 
    {lat: 55, lng: 55},   // 2nd Location - MATCH 
    {lat: 65, lng: 65},   // 3rd Location 
    {lat: 65.01, lng: 65.01}  // 3rd Location 
]

在上面的示例中，結果應該是隻包含第二個位置的數組。假設地點匹配，如果他們在0.2緯度/ lng以內。

我的當前的解決方案是：

獲取的第一項
環路直通的剩餘位置的位置，並且該位置是從第一位置，從該指數slice陣列不同位置
環路直通的剩餘位置，並且該位置是從所述第一，splice陣列不同，以除去剩餘

這裏是一個草率執行它：

var locations = [ 
 
    {lat: 45, lng: 45}, 
 
    {lat: 45.01, lng: 45.01}, 
 
    {lat: 55, lng: 55}, 
 
    {lat: 55.01, lng: 55.01}, 
 
    {lat: 54.99, lng: 54.99}, 
 
    {lat: 55, lng: 55}, 
 
    {lat: 65, lng: 65}, 
 
    {lat: 65.01, lng: 65.01} 
 
]; 
 

 
const startingLocation = locations.splice(0,1)[0]; 
 

 
const first = locations.findIndex(location => { 
 
    const { lat, lng } = location; 
 
    return newLocation(startingLocation.lat, startingLocation.lng, lat, lng); 
 
}); 
 

 
const validLocations = locations.slice(first); 
 

 
const newLatLng = validLocations[0]; 
 

 
const last = validLocations.findIndex(location => { 
 
    const { lat, lng } = location; 
 
    return newLocation(newLatLng.lat, newLatLng.lng, lat, lng); 
 
}); 
 

 
if (last > -1) { 
 
    validLocations.splice(last); 
 
} 
 

 
console.log(validLocations) 
 

 
// Helper function to test if locations are the same 
 
// For demo purposes only 
 
function newLocation(lat1, lng1, lat2, lng2) { 
 
    return Math.abs(lat1 - lat2) + Math.abs(lng1 - lng2) > 1 
 
}

這需要多個環路直通的位置，且難以效仿。有沒有辦法通過減少時間複雜度和/或使其更易於理解來簡化這一點？

來源

2017-10-10 Brett DeWoody

這基本上是一個[字符串匹配（https://en.wikipedia.org/wiki/String_searching_algorithm），爲此，存在着許多不同的算法。 – Bergi

@Bergi我可以看到它如何使用字符串匹配來解決，但它似乎不是一個很好的解決方案。你能舉一個例子嗎？ –

哦，等等，看來我誤解了你的問題。只有標題「*在數組*中查找連續匹配」使我想起了字符串匹配問題。 – Bergi

您的兩個循環的解決方案簡單，直接，高效。沒有理由對此做任何改變。然而，你不應該經常使用slice和splice任何數組，所以在初始數組中找到匹配的第一個和最後一個索引就足夠了 - 然後在最後一次找到slice。

此外代碼可以簡化很多：

const firstMatch = findIndexFrom(locations, differentTo(locations[0]), 1); 
if (firstMatch == -1) return []; 
const afterMatch = findIndexFrom(locations, differentTo(locations[firstMatch]), firstMatch+1); 
if (afterMatch == -1) return locations.slice(firstMatch); 
else     return locations.slice(firstMatch, afterMatch); 

function differentTo(target) { 
    return function(location) { 
    return Math.abs(target.lat - location.lat) + Math.abs(target.lng - location.lng) > 1; 
    }; 
} 
function findIndexFrom(arr, pred, index) { // unfortunately the native `findIndex` doesn't take a start position like `indexOf` 
    for (; index < arr.length; index++) 
    if (pred(arr[index], index)) 
     return index; 
    return -1; 
}

來源

2017-10-17 17:16:03 Bergi

查找陣列中的連續匹配位置

回答

相關問題