线性传递数组让我难过

Question

您好，我正在尝试对两个数组进行一次线性传递，这是我的问题：我让它与注释代码一起工作，但它不正确。在寻求帮助之前，我已经尝试解决这个问题整整一夜 - 这是我尝试过的方法：

////////////////////////////// PROBLEM STATEMENT //////////////////////////////
// Given two arrays of ints sorted in increasing order, outer and inner,     //
// print true if all of the numbers in inner appear in outer. The best       //
// solution makes only a single "linear" pass of both arrays, taking         //
// advantage of the fact that both arrays are already in sorted order.       //
//   {1, 2, 4, 6}, {2, 4} -> true                                            //
//   {1, 2, 4, 6}, {2, 3, 4} -> false                                        //
//   {1, 2, 4, 4, 6}, {2, 4} -> true                                         //
///////////////////////////////////////////////////////////////////////////////

  // >>>>>> Your Java Code Fragment starts here <<<<<<
  Boolean prez = true;
  Scanner kb = new Scanner(System.in);
  int n = kb.nextInt(); int z = 0;
  int[] inner = new int[n]; for(int i = 0; i < inner.length; i++)inner[i] = kb.nextInt();
      n = kb.nextInt();
  int[] outer = new int[n]; for(int i = 0; i < outer.length; i++)outer[i] = kb.nextInt();
//   if(outer.length == 0)
//     prez = true;   
//  for(int i = 0; i < outer.length; i++){
//    for(int o = 0; o < inner.length ; o++){
//      if(outer[i] != inner[o]){
//        prez = false;
//      } if(outer[i] == inner[o]){
//        prez = true;
//        break;
//      }
//    }
//    if(i == 1 && outer[i] == 3){
//       prez = false;
//       break;
//    }
//  }
//  for(z = 0; z < outer.length ; z++){
//    if(inner[z] == outer[z]){ 
//      z++;
//      prez = true;
//    }else if(outer[z] != inner[z]){
//      prez = false;
//    }
//  }


  int i = 0;
//ok lodo so we loop through the array
for(int j = 0; j < inner.length; j++)
{
//while i is less than the outer length and out[i] is less than inner[j]??? 
    while(i < outer.length && outer[i] < inner[j])
    {
    //we increase i 1
       i++;
    }
// if "i" is the same or equal to outer size or the current outer doesnt equal inner make prez false 
    if(i >= outer.length || outer[i] != inner[j])
    {
         prez = false;

    }
}
//prez = true;
//print the results
System.out.print(prez);

我理解正确吗？这是输出

我正在尝试 lodo 的解决方案。这是输出当我得到一个假的时候我需要休息吗？

Answer 1

您需要对内部数组进行一次循环，并为外部数组创建一个外部索引：

boolean checkContained(int[] inner, int[] outer)
{
    int i = 0;
    for(int j = 0; j < inner.length; j++)
    {
        while(i < outer.length && outer[i] < inner[j])
        {
             i++;
        }
        if(i >= outer.length || outer[i] != inner[j])
        {
             return false;
        }
    }
    return true;
}

编辑：

此外（正如我在您的输出示例中看到的），您必须先读取外部数组，而在您的代码中您首先读取内部数组：

int n = kb.nextInt(); int z = 0;
int[] outer= new int[n]; for(int i = 0; i < inner.length; i++)inner[i] = kb.nextInt();
  n = kb.nextInt();
 int[] inner= new int[n]; for(int i = 0; i < outer.length; i++)outer[i] = kb.nextInt();

Answer 2

您可以管理 2 个索引或 2 个迭代器，每个数组一个。具有 2 个索引的解决方案：

boolean ok = true;
int outerIndex = 0;
int innerIndex = 0;
while (ok && outerIndex < outer.length && innerIndex < inner.length) {
   if (outer[outerIndex]==inner[innerIndex]) {
      outerIndex++;
      innerIndex++;
   }
   else if (outer[outerIndex] < inner[innerIndex]) {
      outerIndex++;
   }
   else {
      ok = false;
   }
}
// test if there are remaining values in inner array
if (innerIndex < inner.length) {
   ok = false;
}
// here ok is true if all inner values have been found in outer

Answer 3

你会如何在纸上做到这一点？

您将从头开始遍历两个数组，管理两个独立的索引。对于第一次迭代，两个索引都为零。

现在，您有 3 种可能性：

两个数组中0处的数字相等
外层数组中的数字更高
内部数组中的数字更高

所以在 1. 下，我们可以简单地增加两个索引并比较结果两个数字。

在3.下，我们知道外层数组是有序的，我们可以递增外层数组的索引并比较结果两个数。希望能找到更高的价值。

在2下，我们知道内部数组已排序，我们知道外部数组不能包含该值，我们可以立即中止。

从逻辑上我们可以看出我们只需要一个循环，我们只增加索引，并且我们总是至少增加一个索引（或退出）。所以我们最多要做的就是遍历两个数组一次——使这个算法线性化。

因此代码的框架如下所示：

public static boolean containsAll(int[] outer, int[] inner) {
    int outerIdx = 0;
    int innerIdx = 0;
    while (outerIdx < outer.length && innerIdx < inner.length) {
        final int o = outer[outerIdx];
        final int n = inner[innerIdx];
        if (o == n) {
            //elements are equal - situation 1.
        } else if (o > n) {
            //outer element greater than inner - situation 2.
        } else if (n > o) {
            //inner element greater than outer - situation 3.
        }
    }
    //do we need to check anything here?
}

Answer 4

这是我的回答，希望它能解释我添加的评论中的所有内容

public boolean linearIn(int[] outer, int[] inner) {

  int p = 0;//pointer for inner array

  if(inner.length==0)return true;//no inner array

  for(int i=0;i<outer.length;i++){//iterating outer array

    if(inner[p] == outer[i]){//found a inner array element in outer 
      p++;//increment pointer of inner array
    }
    if(p==inner.length){//if everyone in inner array is found
      return true;
    }
  }
  return false;
}

线性传递数组让我难过

Linear pass over an array has me stumped

java

arrays

java.util.scanner