标签: array-algorithms

我有一个问题,一个OK-ish解决方案.我希望那里有更好的解决方案.

问题

我有一个大约200,000个整数的数组.给定两个索引i1和i2,我需要计算i1和i2之间所有元素的总和.数组中的每个整数都介于1和4之间.例如:

a = [1, 3, 2, 4, 3, 2, 4, 1];
subsection_sum(a, 0, 3); // returns 6: (1 + 3 + 2)

此操作将执行大约200,000次,因此需要非常快.for循环中的一个简单计数器是O(n),而且太慢了.在构建之后,阵列永远不会被修改,因此可以拥有相对昂贵的预处理阶段.

迄今为止我的最佳解决方案

该算法在O(log n)时间内工作:

首先用零填充原始数组,直到其长度为2的幂.接下来,将数组拆分为两个相等的部分并存储每个的总和.然后将数组拆分为四分之一并存储每个数组的总和.然后是八分之一.继续这样做,直到数组被分成2个元素长的部分.对于上面的8元素数组,这需要两个步骤:

halves = [(a[0] + a[1] + a[2] + a[3]), (a[4] + a[5] + a[6] + a[7])]
quarters = [(a[0] + a[1]), (a[2] + a[3]), (a[4] + a[5]), (a[6] + a[7])]

然后给出两个索引,现在可以在O(log n)时间内计算出subsection_sum.例如,subsection_sum(a,2,7)== quarters [1] + halfves [1].

对于二叉树，我想获得落在单个垂直线中的所有节点的总和。我想要每个垂直节点中的节点总和

             A
           /    \
          B      C
         /  \   /  \
         D   E  F   G
        / \ 
        H  I

如果你看上面的 T 恤

line 0   A  E F   so sum  = A+E+F
line -1  B I      so sum = B +I
line 1   C        so sum = C
line 2   G        so sum = G

我实现了以下算法

Map<Integer,Integere> mp = new HashMap<Integer,Integer>()
calculate(root,0); 

 void calculate(Node node, int pos){
   if(node==null)
        return ;
  if(mp.containsKey(pos) ){
    int val = mp.get(pos) + node.data;
     mp.put(pos,val);
    }
    else{ 
         mp.put(pos,node.data); …

在一个应用程序中,我测量了一个模式的很多2d坐标(x,y).该图案由网格上的一组点组成,在x和y方向上具有固定的间距.这些坐标都有质量分数,并按此分数排序.我想要做的是首先在x上排序这些坐标,并定义属于一起的x坐标的组(区域).在此步骤之后,我想对y区域中的不同x区域进行排序.

在此之后,我能够将坐标标记为相应的图案(网格)标签.

示例:测量坐标(x,y)=(2,2),(2,3),(1,2),(1,3),(2,1),(1,1),(3,2) ),(3,3),(3,1)

在步骤1之后:(x,y)=(1,2),(1,3),(1,1)(2,2),(2,3),(2,1)(3,2), (3,3),(3,1)

在第2步之后:(x,y)=(1,1),(1,2),(1,3),(2,1),(2,2),(2,3),(3,1) ),(3,2),(3,3)

是否有已执行此任务的排序例程？如果不测量图案的某些坐标,例程也应该有效.

有人可以给我一些线索,我不是一个经验丰富的c ++程序员,但也许有一些提示我可以做这个工作!

我正在观看 Coursera 普林斯顿算法关于合并排序的讲座，我理解所有分析，除了最​​多 6 n log n 数组访问的合并。

为什么是 6？

我们需要在数组中找到最大元素,该元素也等于同一数组中两个元素的乘积.例如[2,3,6,8],这里6 = 2*3,所以答案是6.

我的方法是对数组进行排序,然后使用两个指针方法检查每个元素是否存在产品.这是o(nlog(n))+ O(n ^ 2)= O(n ^ 2)方法.有更快的方法吗？

考虑具有N个元素的整数数组A,其中每个元素与另一个数组元素具有一对一的关系.

对于每个i,其中1≤i≤N,在元素i和元素N-i + 1之间存在1-> 1的关系

任务是对此阵列执行以下操作,如下所示:

给定两个整数(L,R),我们必须将该范围内的每个元素与其相关元素交换.(参见下面的示例说明)

样本输入

5
1 2 3 4 5
2
1 2
2 3

样本输出

5 2 3 4 1

解释对于第一个查询,我们将1与5和2交换为4.现在数组变为 - 5 4 3 2 1

同样现在,对于第二个查询,我们将4与2和3交换.所以最终的阵列将是5 2 3 4 1

我的程序是这样的:

import java.util.Scanner;
public class ProfessorAndOps {

public static void main(String[] args) {
    // TODO Auto-generated method stub

    Scanner in=new Scanner(System.in);
    int n=in.nextInt();//length of array
    int a[]=new int[n];//array declaration
    for(int i=0;i<n;i++){
        //inputting array elements
        a[i]=in.nextInt();
    }
    int q=in.nextInt();//number of queries
    for(int i=0;i<q;i++){
        int …

我有一个程序,它总结了两个数组的共同元素.为此,我使用了两个for循环,如果我有三个,那么我可以使用三个for循环.但是如何总结运行时n中n个数组的公共元素.

我不知道如何在运行时更改循环次数,还是有任何其他相关概念？

这是我试图总结两个数组的代码:

import java.util.Scanner;

public class Sample {
    public static void main(String... args)
    {
        Scanner sc=new Scanner(System.in);
        int arr1[]={1,2,3,4,5},arr2[]={4,5,6,7,8},sum=0;
        for (int i=0;i<arr1.length;i++)
        {
            for (int j=0;j<arr2.length;j++)
            {
                if (arr1[i]==arr2[j])
                {
                    sum+=(arr1[i]);
                }
            }
        }
    }
}

想象一下，有一个整数数组，但不允许您访问任何值（因此不允许Arr[i] > Arr[i+1]或其他）。区分整数的唯一方法是使用query()函数：该函数将元素子集作为输入，并返回该子集中唯一整数的数量。目标是根据整数的值将它们分成组 \xe2\x80\x94 同一组中的整数应具有相同的值，而不同组中的整数应具有不同的值。\n问题 - 代码必须是 O( nlog(n))，或者换句话说，query() 函数只能被调用 O(nlog(n)) 次。

我花了几个小时在 Python 中优化不同的算法，但所有这些算法的复杂度都是 O(n^2)。作为参考，这是我开始的代码：

n = 100\nquerycalls = 0\nsecretarray = [random.randint(0, n-1) for i in range(n)]\ndef query(items):\n    global querycalls\n    querycalls += 1\n    return len(set(items))\ngroups = []\n

secretarray生成一个长度为 的巨大随机数字列表n。querycalls跟踪函数被调用的次数。groups是结果所在。

我做的第一件事是尝试创建一个基于合并排序的算法（将数组拆分，然后根据 query() 值合并），但我永远无法使其低于 O(n^2)。

考虑一个N个整数的数组.找到最长的连续子阵列,使其元素的平均值大于(或等于)给定数量k.

显而易见的答案是O(n ^ 2)复杂度.我们可以做得更好吗？

我目前正在做一个编码挑战,声明:

给定一个单词列表,返回可以在美国键盘的一行上使用字母表键入的单词,如下图所示(这是QWERTY键盘的图像).

例:

Input: ["Hello", "Alaska", "Dad", "Peace"]
Output: ["Alaska", "Dad"]

我为解决这个问题所做的是编写一个for循环,然后执行if将所有行(如QWERTY)替换为的语句,""如果它的长度大于1,则不能在一行中键入该单词.我得到几乎正确的输出,但我的数组包含null元素.

我的输出是:

[null,"Alaska","Dad",null]

如何返回没有这些null元素的数组？为了完成这个挑战,我必须返回一个String[]数组.我不能用一个ArrayList回来.

class Solution {
    public String[] findWords(String[] words) {
    String[] result = new String[words.length];

    String row1 = "qwertyuiop";
    String row2 = "asdfghjkl";
    String row3 = "zxcvbnm";

    for (int i = 0 ; i < words.length; i++) {
        if (words[i].toLowerCase().replaceAll("[" + row1 + "]", "").length() == 0 ||
           words[i].toLowerCase().replaceAll("[" + row2 + "]", "").length() == 0 ||
           words[i].toLowerCase().replaceAll("[" + …