以数学方式旋转有序数数组

Question

假设您在给定域中有一组数字，例如：[-4,4]

又假设这组数字在一个数组中，并且是数字顺序，像这样：

[-4, -3 -2, -1, 0, 1, 2, 3, 4]

现在假设我想为这组数字创建一个新的零点，如下所示：(I select -2 成为我的新轴，所有元素都相应移动）

Original: [-4, -3 -2, -1, 0, 1, 2, 3, 4]

Zeroed: [-2, -1 0, 1, 2, 3, 4, -4, -3]

有了新的归零数组，假设我有一个函数叫做：

"int getElementRelativeToZeroPosition(int zeroPos, int valueFromOriginalArray, int startDomain, int endDomain) {...}"

使用示例：

I am given 3 of the original array, and would like to see where it mapped to on the zeroed array, with the zero on -2.

getElementRelativeToZeroPosition(-2, 3, -4, 4) = -4

无需创建任何数组并为此映射移动元素，我将如何数学产生函数的预期结果以上？

Answer 1

你可以写一个双链表，头节点指向开始

struct nodeItem
{
    nodeItem* pev = nullptr;
    nodeItem* next = nullptr;
    int value = 0;
}

class Node
{
private:
    nodeItem* head;

public:
    void SetHeadToValue(int value);
    ...
}

最后一个值应该指向第一个值的下一个，所以你有一个循环列表。

弄清楚，如果你在列表的末尾，你必须检查该项目是否等于头节点

Answer 2

我会这样做：

获取原始零位索引
获取新零位置的索引（即您示例中的 -2 索引）
获取搜索位置的索引（索引为 3）
计算新零位置和原始零位置之间的移动矢量
将移动向量应用到搜索位置模数数组大小以执行旋转

假设您的数组是从零开始的：

index(0) => 4
index(-2) => 2
index(3) => 7
array_size => 9

move_vector => index(0) - index(-2)
            => 4 - 2 => +2

new_pos(3) => (index(3) + move_vector) modulo array_size
           => (7 + 2) mod 9 => 0

value_at(0) => -4

就是这样

Answer 3

从数学上讲，如果你有一组由包含范围 [start, stop] 给出的隐式整数，选择新的零点的选择实际上是选择一个索引开始。计算完这个索引后，你可以计算你的查询点的索引（在原始域中），并找到它们之间的差异以获得偏移量：

例如：

给定：范围 [-4, 4]，假设零索引数组 (0,...,8) 对应于范围内的值
- 长度（范围）= 4 - (-4) + 1= 9
选择新的 'zero point' of -2。
- -2 的索引是 -2 - (-4) = -2 + 4 = 2
查询位置 3:
- 原始范围内的索引：3 - (-4) = 3 + 4 = 7
在归零数组中找到 3 的偏移量：
- 这是原始数组中索引之间的差异
- 7 - 2 = 5，因此元素 3 与元素 -2 相距五跳。等效地，它是 5-len(range) = 5 - 9 = -4 跳远。你可以选择min(abs(5), abs(-4))看看你更喜欢哪一个。

以数学方式旋转有序数数组

Mathematically rotate an array of ordered numbers

c++

arrays

mapping

performance