标签: array-algorithms

给定一个排序的整数数组,我们怎样才能找到一对总和为K的整数？

例如array = 1,3,5,6,0,K = 6答案是1和5.

应尽量减少时间复杂性.

我正在编写一个代码来查找C中的最大总和连续子数组.根据我的说法,逻辑似乎很好,但输出仍然不正确.请查看代码.该算法将较大的阵列分成2个子阵列.然后通过检查左数组,右数组以及包含中点的数组来检查最大和子数组(它将从中点检查左右,然后返回包含中点的最大和子数组).

int* cross_max(int arr[], int low, int mid, int high)
{
    int left_max, left_sum = -2000;
    int sum = 0;
    int i;
    for(i=mid; i>=low;i--)
    {
        sum = sum + arr[i];
        if(sum > left_sum)
        {
            left_sum = sum;
            left_max = i;
        }
    }


    int right_max, right_sum = -2000;

    for(i=mid+1; i<=high;i++)
    {
        sum = sum + arr[i];
        if(sum > right_sum)
        {
            right_sum = sum;
            right_max = i;
        }
    }

    // 0 - sum
    // indices - 1,2

    int temp_arr[3] = {0,0,0};
    temp_arr[0] …

我正在给自己上数据结构和算法的进修课程（并学习新东西——我在大学主修信息系统而不是计算机科学，所以我没有接受这些方面的正规教育），而且我“一直在研究堆。我有点困惑。

我的理解是堆基本上是一棵半排序树，其中每个子节点的值都保证小于其父节点的值（假设本讨论为 MinHeaps）。那么，如果它是一棵树，为什么我见过的每个实现都在内部使用了类似数组的结构，而不是构建一组树节点？

我必须记住数组中 N 的子节点位于 2N + 1（左）和 2N + 2（右）* 处，这对我来说似乎很奇怪。为什么不直接构建一个具有 Left 和 Right 属性的节点并从那里开始呢？

*来源：本文

这是我的多维数组:

$arrOrg = [2, 3, [5, 7, 1], 100, [6, 9, [14, 95]], 78];

我想从这个数组中获得最高价值.

这是我到目前为止所尝试的:

$highest = 0;
function getHighest($arr) {
    for ($i = 0; $i < count($arr); $i++) {
        if (is_array($arr[$i])) {
            getHighest($arr[$i]);
        } else {
            if ($arr[$i] > $arr[$i + 1]) {
                $highest = $arr[$i];
            } else {
                $highest = $arr[$i + 1];
            }
        }
    }
    return $highest;
}
echo getHighest($arrOrg);

但它给出了一个不正确的结果: 78

你能帮我吗？

这将是一个很长的问题,请在阅读前深呼吸.

我想了解将一维数组的索引转换为多维数组的向量索引的最快算法.

让我们以一个例子来理解我为什么需要它:

我有一个二维数组:数组[i1] [i2]

i1从i1_b = 0运行到i1_e = 2

i2从i2_b = 0运行到i2_e = 1

所以这个数组逐行输出到文件中:

阵列[0] [0]

阵列[0] [1]

阵列[0] [2]

阵列[1] [0]

阵列[1] [1]

阵列[1] [2]

现在我逐行读取文件,索引k是最后读取的行号.

我读了第一行,即Array [0] [0]和k = 0

我读了第二行,即Array [0] [1]和k = 1

...

可以注意到k将从k_b = 0运行到k_e = 5和

k = 0将对应于i1 = 0,i2 = 0

k = 1将对应于i1 = 0,i2 = 1

...

问题:所以我的问题是如何以最快的方式将k转换为i1和i2？(我在阅读文件时不需要它,但稍后在我的程序中)

在这个例子中,其中一个解决方案是

i1 = k /(i1_e - i1_b + 1);

i2 = k%(i1_e - i1_b + 1);

问题1:就周期和计算机时间而言,它是否是最快的解决方案？

好.问题2:我们如何将此算法推广到多维数组？

阵列[I1] …

考虑两个查找函数:

simple={1,3,5}

function isX(id) 
 for _,v in ipairs(simple) do 
  if v==id then return true end 
 end 
 return false 
end


assoc={[1]=true,[3]=true,[5]=true}

function isX2(id) 
 return assoc[id] or false 
end

哪个函数的查找成本较低？或者他们是平等的？Lua如何在内部存储关联数组？

我正在尝试解决以下练习:

不使用反向方法反转数组,不使用第二个数组,也不重复任何值.

我已经考虑过将数组作为一个对象,然后从最后到开始更新数组,但我想你也可以更新它.

尝试过简单的事情:

function reverseArray(array) {
  for (var i = 0; i < array.length; i++) {
    // var elem = array.shift();
    var elem = array.shift()
    array.push(elem)
  }
  return array
}

array = ['a', 'b','c','d','e'];

reverseArray(array);

但这并没有真正改变它.有关如何做到这一点的任何建议或解释？

我需要打印一个int数组的任何两个元素之间的最小差异。

数组的每个元素A小于等于其长度。

1 <= A[i] <= A.length;

我已经在Java中尝试了以下给定的方法-但是，当数组大小为〜10 ^ 5时，这需要1秒钟以上的时间才能找到结果。

我认为这可能是一种幼稚的方法。有什么办法可以进一步优化它？能做到O(n)时间复杂吗？

static int findResult(int[] arr)
        {
                 int max =  Integer.MAX_VALUE;
                 HashSet<Integer> hs = new HashSet<Integer>();
                 for(int obj : arr)
                 {
                     hs.add(obj);
                 }
                if(hs.size()==1 )
                {
                    return 0;             // if all elements are same
                }
                 for(int i=0; i<arr.length; i++)
                 {  
                     for(int j=i+1; j<arr.length; j++)
                     {
                         int value = Math.abs(a[i]-a[j]);
                         if(value<max)
                         {
                            max = value;
                         }

                      }         
                }
        return max;  // returns the smallest positive difference
    }

我有这个代码,它采用格式为255.255.255.255的IP地址(字符串),并需要对这些数字(此处未发布)执行一些后处理,但必须将字符串转换为整数数组.

我在这里使用了split()方法,但它没有给我结果.我在sp上做了正则表达式的其他答案,但没有一个对我有效.

import java.util.Scanner;
public class Main{
    public static void main(String args[]){
        String text;

        Scanner take=new Scanner(System.in);
        text=take.nextLine();
        String data[]=text.split(".",4);

        for(String w:data){
            System.out.println(w);
        }
        take.close();
    }
}

我已尝试输入12.36.26.25

但它输出36.26.25,应该是12 36 26 25

我想检查列表值是否具有某种程度的"亲密度".有一个很好的算法来做到这一点？奖励积分为最pythonic方式.

有效

[1,7,8,9]
[3,4,100,101,102,103,104,105]

无效

[1,8,9]
[1,10]
[100,200,300,400,500]