-1

ios 项目 https://github.com/HarrisonJackson/iOS-find-top-4-integers-in-big-list---also-use-blocks-and-delegates

该算法应该解决未排序数组中的前 4 个整数。在这里，我生成了一个未排序的 NSNumber 列表并对其进行迭代——保持前 4 个列表。我向代码挑战提交了解决方案，但被告知该解决方案实际上不是 O(n)。 

// Generate the array self.numbers and unset the top 4 self.topN
// ...
// Use built in fast-enumeration to iterate over array of NSNumbers
    for (NSNumber * num in self.numbers) {
      // Make sure that all 4 of the top4 numbers is initialized
        if(!self.top1){
            self.top1 = num;
            continue;
        }
        if(!self.top2){
            self.top2 = num;
            continue;
        }
        if(!self.top3){
            self.top3 = num;
            continue;
        }
        if(!self.top4){
            self.top4 = num;
            continue;
        }

      // Adjust our top4 as we fly over the array
        if([self.top1 intValue] < [num intValue]){
            self.top1 = num;
            continue;
        }
        if([self.top2 intValue] < [num intValue]){
            self.top2 = num;
            continue;

        }
        if([self.top3 intValue] < [num intValue]){
            self.top3 = num;
            continue;

        }
        if([self.top4 intValue] < [num intValue]){
            self.top4 = num;
            continue;

        }

    }

更新感谢您的快速响应-问题似乎不在于算法的复杂性，而在于逻辑。当发现更大的值时，我并没有将数字推到前 4 位 - 哎呀！哈哈。这是针对任何有类似问题的人的更新算法。我也会发布我的完整项目解决方案。

for (NSNumber * num in self.numbers) {
      // Make sure that all 4 of the top4 numbers are initialized
        if(!self.top1){
            self.top1 = num;                
            continue;
        }
        if(!self.top2){
            self.top4 = self.top3;
            self.top3 = self.top2;
            self.top2 = num;
            continue;
        }
        if(!self.top3){
            self.top3 = num;
            continue;
        }
        if(!self.top4){
            self.top4 = num;
            continue;
        }

      // Adjust our top4 as we fly over the array
        if([self.top1 intValue] < [num intValue]){
            self.top4 = self.top3;
            self.top3 = self.top2;
            self.top2 = self.top1;
            self.top1 = num;
            continue;
        }
        if([self.top2 intValue] < [num intValue]){
            self.top4 = self.top3;
            self.top3 = self.top2;
            self.top2 = num;
            continue;

        }
        if([self.top3 intValue] < [num intValue]){
            self.top4 = self.top3;
            self.top3 = num;
            continue;

        }
        if([self.top4 intValue] < [num intValue]){
            self.top4 = num;
            continue;

        }

    }
4

1 回答 1

1

逻辑是错误的，但算法是 O(n)。对于每一步，只有恒定数量的操作。

逻辑错误是，当您在某个位置替换数字时，您需要将先前的值向下推，例如

   if([self.top1 intValue] < [num intValue]){
        self.top4 = self.top3;
        self.top3 = self.top2;
        self.top2 = self.top1;
        self.top1 = num;
        continue;
    }
于 2013-04-29T21:26:07.777 回答